Statistical analysis of the effect the initial order of an array has on the performance of a sorting algorithm
Thomas C. McMillan, Ivan B. Liss · Proceedings of the 17th conference on ACM Annual Computer Science Conference · 1989
We consider, in this paper, various algorithms which are known to sort an array in O(n2) or O(n log n) time. Since the analysis of an algorithm may indicate its average performance, it is desirable to identify conditions which would indicate that a certain algorithm should be used even though its performance characteristics are worse, on average, than those of other algorithms. This paper investigates the effect that the initial order of an array has on the performance characteristics of algorithms used to sort the array.