Worst-Case Number of Comparisons in Sorting

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Worst-Case Number of Comparisons in Sorting

Nitin Verma

November 30, 2021

Insertion Sort, Selection Sort, Quick Sort and Merge Sort are a few examples of Comparison-based Sorting Algorithms. Let us denote by A any algorithm in this class of sorting algorithms. In this article, we will create a model of algorithm A and ﬁnd out how to construct an adverse input for A using this model. This will help us in ﬁnding a lower-bound on the number of comparisons which A must do in the worst-case.

Let a = (a₀,a₁,a₂,…,a_n−1) be an array of n distinct elements, which needs to be sorted by A in increasing order using a comparison function f. For any two elements a_i and a_j, f(a_i,a_j) will return true to indicate a_i < a_j, and false otherwise. Since A is a comparison-based sorting algorithm, the only information about the elements which it can use for sorting is their pairwise order obtained using f; it cannot use the value of their keys directly.

Since A can be any comparison-based sorting algorithm, we don’t know how it actually works; its structure, loops and conditionals are all unknown. We only know that it would do a sequence of comparisons and output a permutation of the elements of a which is sorted. There are total n! possible permutations of the n elements of a, and exactly 1 of them is sorted.

[Next]