Sorting algorithms are the means to sort a given set of data in an order according to the requirement of the user. They are primarily used to sort data in an increasing or decreasing manner. There are two types of sorting algorithms:
- Comparison-based sorting algorithms
- Non-comparison-based sorting algorithms
Comparison-based sorting algorithms: The elements of an array are compared to each other to sort the array. This type of algorithm checks if one element is greater than or equal to another element in the array. It does not do manipulation on a single array element.
Examples of comparison-based algorithms: Merge sort (compare the elements and copy them), Quicksort (compare the elements and swap them), and Heap sort (Heapify the elements using comparison).
Theorem: Every comparison-based sorting algorithm has the worst-case running time of
Proof:
Let us assume a comparison-based sorting algorithm, and an array of length N. Consider the input array contains array elements like 
in some jumbled order. We can order these N elements in N! different ways.
- Assumptions:
- Proof: By the Pigeonhole principle: If n items are put into m containers, with n > m, then at least one container must contain more than one item.
- Here, the pigeon is N! different inputs. The holes are 2K different executions.
- If
*** QuickLaTeX cannot compile formula: *** Error message: Error: Nothing to show, formula is empty
, This means the algorithm executes identically on 2 distinct inputs, and we can’t have a common execution of the sorting algorithm, which is averse to our assumption of a sorting algorithm.
- Since the sorting method is correct, 2K ≥ N! ≥ (N/2)N/2, because there are at least N/2 terms in N * (N – 1) * . . . * 2 * 1 that has a value of at least N/2.
- Taking log base 2 on both sides, K = (N/2)log2(N/2)
- Hence, every comparison-based sorting algorithm has the worst-case running time that can never be better than
.
.