Towards a Realistic Analysis of Some Popular Sorting Algorithms

Source abstract

We describe a general framework for realistic analysis of sorting algorithms, and we apply it to the average-case analysis of three basic sorting algorithms ( QuickSort , InsertionSort , BubbleSort ). Usually the analysis deals with the mean number of key comparisons, but here we view keys as words produced by the same source, which are compared via their symbols in lexicographic order. The ‘realistic’ cost of the algorithm is now the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons used by the algorithm. For sorting algorithms, and with respect to key comparisons, the average-case complexity of QuickSort is asymptotic to 2 n log n , InsertionSort to n 2 /4 and BubbleSort to n 2 /2. With respect to symbol comparisons, we prove that their average-case complexity becomes Θ ( n log 2 n ), Θ( n 2 ), Θ ( n 2 log n ). In these three cases, we describe the dominant constants which exhibit the probabilistic behaviour of the source (namely entropy and coincidence) with respect to the algorithm.