1. Sorting Algorithms
Sorting algorithms impose a total order on an unordered sequence. They are among the most studied algorithms in computer science: many other algorithms (binary search, Kruskal's MST, many DP formulations) require sorted input as a precondition, so efficient sorting is foundational rather than incidental.
1.1 Algorithms
| Algorithm | Paradigm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|---|
| Merge Sort | Divide and conquer | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n)\) | Yes |
| Quick Sort | Divide and conquer / Randomised | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n^2)\) | \(O(\log n)\) | No |
| Heap Sort | Heap data structure | \(O(n \log n)\) | \(O(n \log n)\) | \(O(n \log n)\) | \(O(1)\) | No |
1.2 Lower Bound
The comparison-based sorting lower bound states that any algorithm that sorts \(n\) elements purely by pairwise comparisons requires at least \(\Omega(n \log n)\) comparisons in the worst case. The argument uses a decision-tree model: a binary tree with \(n!\) leaves (one per permutation) must have height at least \(\log_2(n!) = \Omega(n \log n)\) by Stirling's approximation. Merge sort and heap sort achieve this bound; quick sort achieves it on average. Non-comparison sorts (radix, counting, bucket) bypass the lower bound by exploiting key structure.