Encroaching Lists as a Measure of Presortedness is the title of a 1988 paper by Skiena that describes the concept of encroaching lists, how to generate them from a sequence, how they can be used as a measure of presortedness $Enc$, and then describes the Melsort sorting algorithm, which is adaptative with regard to $Enc$.
Basically, given a sequence, one can build a sequence of encroaching lists: for every element in the original sequence, compare it to the head of the first encroaching list and add it to the front of it if it's not greater than the head, otherwise compare it to the tail of the first encroaching list, and add it to the end of that list if the element in greater than the tail. If the element is neither smaller than the head or greater than the tail, try with the next encroaching list, etc... eventually, if it doesn't match any existing encroaching list, create a new one and add the element in.
This description is a bit rough, so here is an easier example (1): the sequence $\{6, 7, 1, 8, 2, 5, 9, 3, 4\}$ will result into three encroaching lists: $\{1, 6, 7, 8, 9\}$, $\{2, 5\}$ and $\{3, 4\}$.
Skiena asserts that the number of encroaching lists can be used as a measure of presortedness; another paper even shows as an example that $Enc(\{6, 7, 1, 8, 2, 5, 9, 3, 4\}) = 3$.
However the paper Right invariant metrics and measures of presortedness by Estivill-Castro, Mannila and Wood formally define measures of presortedness, and one of the main definitions (2) is the following (let $X$ be a sequence and $M$ a measure of presortedness):
If $X$ is in ascending order, $M(X) = 0$.
If we follow the logic of the previous example (1), $Enc(\{0, 1, 2, 3, 4, 5, 6\}) = 1$ because there is only one resulting encroaching list containing the full sorted sequence. However, if $Enc$ as described was a measure of presortedness, then we should have $Enc(\{0, 1, 2, 3, 4, 5, 6\}) = 0$ per the given definition (2).
So, shouldn't $Enc$ instead correspond to the number of encroaching lists generated from a sequence minus one in order to be a proper measure of presortedness? I can't find more details about that in any paper.
