A sorting algorithm that runs in O(n+min(n log t, r log (r+1))) time, where t is the number of runs up and runs down in the input sequence of n elements and r is the smallest number of exchanges of two arbitrary elements required to sort the sequence, is presented. The memory requirements of the algorithm are modest: an integer array of size n+1 is required to accommodate the main data structures. In the worst case, i.e. when no presortedness is assumed, the actual running time compares favorably to that of the fastest sorting algorithms.
展开▼
