Efficient sample sort and the average case analysis of PEsort

AbstractThe purpose of the paper is twofold. First, we want to search for a more efficient sample sort. Secondly, by analyzing a variant of Samplesort, we want to settle an open problem: the average case analysis of Proportion Extend Sort (PEsort for short). An efficient variant of Samplesort given in the paper is called full sample sort. This algorithm is simple. It has a shorter object code and is almost as fast as PEsort. Theoretically, we show that full sample sort with a linear sampling size performs at most nlogn+O(n) comparisons and O(nlogn) exchanges on the average, but O(nlog2n) comparisons in the worst case. This is an improvement on the original Samplesort by Frazer and McKellar, which requires nlogn+O(nloglogn) comparisons on the average and O(n2) comparisons in the worst case. On the other hand, we use the same analyzing approach to show that PEsort, with any p>0, performs also at most nlogn+O(n) comparisons on the average. Notice, Cole and Kandathil analyzed only the case p=1 of PEsort. For any p>0, they did not. Namely, their approach is suitable only for a special case such as p = 1, while our approach is suitable for the generalized case