Encroaching lists as a measure of presortedness

Encroaching lists are a generalization of monotone sequences in permutations. Since ordered permutations contain fewer encroaching lists than random ones, the number of such listsm 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 complexityO(nlogm). Thus it is linear for well ordered sets and reduces to mergesort andO(nlogn) in the worst case.This work was partially supported by National Science Foundation Grant CCSR-8714565.