Peaksort

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.