Encroaching lists as a measure of presortedness (Q1115201)

Encroaching lists are a generalization of monotone sequences in permutations. Since ordered permutations contain fewer encroaching lists than random ones, the number of such lists m provides a measure of presortedness with advantages over others in the literature. Experimental and analytic results are presented to cast light on the properties of encroaching lists. Also, we describe a new sorting algorithm, melsort, with complexity O(n log m). Thus it is linear for well ordered sets and reduces to mergesort and O(n log n) in the worst case.