When sorting a multiset of N elements with n < N distinct values, considerable savings can be obtained from an algorithm which sorts in time O(N log n) rather than O(N log N). In a previous paper, two Quicksort derivatives operating on linked lists were introduced which are stable, i.e. maintain the relative order of equal keys, and which achieve the previously unattainable lower bound in partition exchange sorting. Here, six more algorithms are presented which are unstable but operate on arrays. One of the algorithms is also designed for a speedup on presorted input. The algorithms are analyzed and compared to potential contenders in multiset sorting.
It in turn refers to a paper by Jon L. Bentley and M. Douglas McIlroy, "Engineering a Sort Function", Software Practice and Experience, Vol. 23(11), 1249-1265 (November 1993). This paper uses one of the six variants above to refine the UNIX qsort function to come up with a faster and equally safe algorithm. Jon had previously mentioned my one-way partition scheme in his Programming Pearls series for CACM.