\(\newcommand{\Set}[1]{\{#1\}}\) \(\newcommand{\Setdef}[2]{\{{#1}\mid{#2}\}}\) \(\newcommand{\PSet}[1]{\mathcal{P}(#1)}\) \(\newcommand{\Card}[1]{{\vert{#1}\vert}}\) \(\newcommand{\Tuple}[1]{(#1)}\) \(\newcommand{\Implies}{\Rightarrow}\) \(\newcommand{\Reals}{\mathbb{R}}\) \(\newcommand{\Seq}[1]{(#1)}\) \(\newcommand{\Length}[1]{{\vert{#1}\vert}}\) \(\newcommand{\Arr}[1]{[#1]}\) \(\newcommand{\Floor}[1]{{\lfloor{#1}\rfloor}}\) \(\newcommand{\Ceil}[1]{{\lceil{#1}\rceil}}\) \(\newcommand{\Path}[1]{(#1)}\) \(\newcommand{\IRange}[2]{[#1\,..\,#2]}\) \(%\newcommand{\Lg}{\lg}\) \(\newcommand{\Lg}{\log_2}\) \(\newcommand{\BigOh}{O}\) \(%\newcommand{\BigOh}{\mathcal{O}}\) \(\newcommand{\Oh}[1]{\BigOh(#1)}\)

Asymptotic lower bounds for comparison-based sorting algorithms

When considering asymptotic running times, how far from the optimal is, for instance, mergesort?

Let us assume a sorting algorithm such that the following holds.

1. It can compare two elements for (in)equality with the operations \(=\), \(<\), \(\le\), \(>\), and \(\ge\). For instance, a Scala sorting algorithm implementation that uses the Ordering trait interface to compare elements falls under this assumption.

2. But it does not use any other information, such as their binary encodings, about the elements.

Such sorting algorithm is called a “comparison sort” algorithm. For instance, the following are comparison sort algorithms:

• ​ Insertion sort

• ​ Selection sort

• ​ Mergesort

• ​ Quicksort

• ​ heapsort algorithm

For comparison sorts we can get the following asymptotic lower bound for the numbers of comparisons that any comparison sort algorithm must make in the worst case.

Sorting an array of \(n\) elements requires \(\Omega(n \Lg n)\) comparisons in the worst case.

The proof is not included in the course, please see Section 8.1 in Introduction to Algorithms (Aalto access) for it.