Proportion extend sort

PROPORTION EXTEND SOR is a new sorting algorithm, the basic principle of which is similar to PROPORTION SPLIT SORT. This algorithm sorts a sequence by constructing three subproblems, using a QuickSort-like pivot technique and solving recursively each subproblem. The original problem and three subproblems all are of such a structure: a sorted subsequence followed by an unsorted subsequence. The size of the original problem always equals the size of the third subproblem, but in general, the sorted subsequence of the third subproblem is p + 1 times as much as the sorted subsequence of the original, where p is a xed positive constant. The worst case number of comparisons required by this algorithm is less than 1/log(1 + 1/(2p(2) + 2p-1))n log n for p greater than or equal to 1. Empirical results show that the average number of comparisons is close to n log n-O(n) for some p. From our experiments for sorting integers, when p = 16, this algorithm is yet faster, on average, than PROPORTION SPLIT SOR which is faster than CLEVER QUICKSORT.