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.

  • $\begingroup$ If you want a sorted list to have metric value 0, subtract 1 from the encroaching lists metric? $\endgroup$
    – D.W.
    Commented Mar 27, 2016 at 17:11
  • $\begingroup$ @D.W. Well, that's what I'm proposing in the last paragraph. $\endgroup$
    – Morwenn
    Commented Mar 27, 2016 at 17:37
  • 1
    $\begingroup$ OK, sorry, I missed that. It sounds like you know the solution, so I'm not sure what more there is to say. $\endgroup$
    – D.W.
    Commented Mar 27, 2016 at 17:47
  • 1
    $\begingroup$ @D.W. I just hoped somebody would knows about the topic could confirm that I'm not misreading things :) $\endgroup$
    – Morwenn
    Commented Mar 27, 2016 at 18:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.