How Good Sorts Go Bad
William J. Collins, T'seliso E. Mosiuoa · Computer Science Education · 1992
This article presents techniques for generating permutations of 1. N that yield the worst case for several fast sorting algorithms. Specifically, we investigate an improved version of Quicksort, TreeSort, recursive and iterative versions of MergeSort, and HeapSort. In each case, a worst‐case permutation is developed. Such permutations are needed to analyze the worst‐case, run‐time behavior of these sorting algorithms. The results of comparing the worst‐case and average‐case performance are reported, and these results confirm the Big‐O analysis.