Sorting
How each classic sorting algorithm works, what it costs in comparisons and moves, which ones are stable or in place, and how production libraries combine them.
What you will learn
How each classic sorting algorithm works, what it costs in comparisons and moves, which ones are stable or in place, and how production libraries combine them.
Prerequisites: Modules 2, 5 and 17.
Comparison sorting
Quicksort: pivot choice, partition schemes, randomized pivot, worst-case behavior.
Introsort and the practical combination of quicksort, heapsort, and insertion sort.
TimSort concept and stable-run merging.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
The table is the real comparison count for each algorithm on 2000 keys. Things to notice:
Bubble and insertion sort are adaptive: on sorted input they stop after n − 1 comparisons; on reversed input they do about n²/2.
Selection sort always does exactly n(n−1)/2 comparisons, whatever the input.
Quicksort with the last element as pivot degrades to n²/2 on sorted and reversed input (each partition peels off one element); a random pivot keeps it close to n log₂ n (about 23–26 thousand comparisons here) on every input — the expected count is below 2n ln n ≈ 1.39 n log₂ n.
Merge sort and heap sort stay Θ(n log n) on all three.
#include <bits/stdc++.h>
using namespace std;
long long cmps; // comparisons counted through less()
bool less_(int a, int b) { ++cmps; return a < b; }
void bubble(vector<int>& a) {
for (size_t n = a.size(); n > 1; --n) {
bool swapped = false;
for (size_t i = 0; i + 1 < n; ++i) if (less_(a[i + 1], a[i])) { swap(a[i], a[i + 1]); swapped = true; }
if (!swapped) break; // adaptive: already sorted
}
}
void selection(vector<int>& a) {
for (size_t i = 0; i < a.size(); ++i) {
size_t m = i;
for (size_t j = i + 1; j < a.size(); ++j) if (less_(a[j], a[m])) m = j;
swap(a[i], a[m]);
}
}
void insertion(vector<int>& a) {
for (size_t i = 1; i < a.size(); ++i) {
int x = a[i]; size_t j = i;
while (j > 0 && less_(x, a[j - 1])) { a[j] = a[j - 1]; --j; }
a[j] = x;
}
}
void mergeSort(vector<int>& a, vector<int>& tmp, int l, int r) { // [l, r)
if (r - l < 2) return;
int m = l + (r - l) / 2;
mergeSort(a, tmp, l, m); mergeSort(a, tmp, m, r);
int i = l, j = m, k = l;
while (i < m && j < r) tmp[k++] = less_(
…comparisons for n = 2000 (n log2 n is about 21931, n^2/2 = 2000000)
algorithm random sorted reversed
bubble 1997404 1999 1999000
selection 1999000 1999000 1999000
insertion 1002986 1999 1999000
merge 19400 10864 11088
quick (last pivot) 24425 1999000 1999000
quick (random pivot) 23703 22866 25819
heap 37729 39159 35964Non-comparison sorting
Teach assumptions: key range, digit representation, distribution, and stability.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Counting sort runs in O(n + K) for keys in [0, K) — excellent when K is small, useless when K is 2³². Radix sort applies a stable counting sort digit by digit from least significant: O(d·(n + base)), here 4 passes of base 256. Stability is essential: each pass must keep the order produced by the previous, less significant passes. Bucket sort distributes values into ranges and sorts each bucket; it is linear on average only if the input is spread evenly.
#include <bits/stdc++.h>
using namespace std;
// stable counting sort of (key, label) pairs by key in [0, K)
vector<pair<int, char>> countingSort(const vector<pair<int, char>>& a, int K) {
vector<int> cnt(K + 1, 0);
for (auto& p : a) ++cnt[p.first + 1];
for (int k = 0; k < K; ++k) cnt[k + 1] += cnt[k]; // cnt[k] = first output slot for key k
vector<pair<int, char>> out(a.size());
for (auto& p : a) out[cnt[p.first]++] = p; // left-to-right keeps equal keys in order
return out;
}
// LSD radix sort of 32-bit unsigned values, base 256: four stable counting passes
void radixSort(vector<uint32_t>& a) {
vector<uint32_t> tmp(a.size());
for (int shift = 0; shift < 32; shift += 8) {
array<size_t, 257> cnt{};
for (uint32_t x : a) ++cnt[((x >> shift) & 255) + 1];
for (int i = 0; i < 256; ++i) cnt[i + 1] += cnt[i];
for (uint32_t x : a) tmp[cnt[(x >> shift) & 255]++] = x;
a.swap(tmp);
}
}
int main() {
vector<pair<int, char>> a = {{3, 'a'}, {1, 'b'}, {3, 'c'}, {0, 'd'}, {1, 'e'}};
cout << "counting sort (stable):";
for (auto [k, c] : countingSort(a, 4)) cout << ' ' <<
…counting sort (stable): 0d 1b 1e 3a 3c
radix sort of 1e6 random 32-bit values equals std::sort: trueSorting properties
Stable/unstable, in-place/not in-place, adaptive/non-adaptive, comparison/non-comparison, online/offline, internal/external sorting.
Required comparison table
For each algorithm, document best/average/worst time, auxiliary space, stability, in-place status, and suitable use cases. Avoid claiming every implementation has identical complexity.
Bubble (with early exit) teaching; nearly sorted tiny inputs minimising writes (n − 1 swaps) small or nearly sorted input; inner loop of hybrids O(n) arrays, O(log n) lists stable sorting, linked lists, external sorting Quicksort (random pivot) O(n²) (unlikely) O(log n) stack expected general in-memory sorting guaranteed bound with no extra memory small integer key range fixed-width integers or strings
std::sort is introsort: quicksort that switches to heap sort if recursion gets too deep (guaranteeing O(n log n)) and finishes small ranges with insertion sort. std::stable_sort is a merge sort. Python's sorted and Java's object sort use TimSort, which finds existing ascending runs and merges them — fast on partially sorted real data.
Advanced sorting topics
External merge sort, k-way merge, inversion counting, sorting linked lists, custom ordering, partial sorting, nth_element, and comparison lower bounds.
External sort: sort chunks that fit in memory, write them as runs, then k-way merge the runs with a heap (Module 14) — the method for data larger than RAM.
Partial sorting: partial_sort gives the smallest k in order in O(n log k); nth_element places the k-th element in expected O(n) (quickselect).
Inversion counting: during merge sort, when an element from the right half is taken before m − i remaining left elements, it forms m − i inversions (Module 20).
Quiz
? Which algorithms did exactly n − 1 = 1999 comparisons on already-sorted input in the run? (select all that apply)
+ Bubble sort with early exit :: One pass, no swaps, stop.
+ Insertion sort :: Each element compared once with its predecessor.
- Selection sort :: Always n(n−1)/2.
- Heap sort :: Θ(n log n) regardless.
? Why did quicksort with the last element as pivot take about 2 million comparisons on sorted input?
+ The pivot is always the maximum, so each partition removes only one element — Θ(n²). :: A random pivot avoids this.
- Sorted input is invalid for quicksort. :: It is valid, just a bad case.
- The comparison counter was wrong. :: It matched n²/2.
- Quicksort is always Θ(n²). :: Not with good pivots.
? Why must the per-digit sort in LSD radix sort be stable?
+ Otherwise a later pass would scramble the order established by less significant digits. :: Stability carries earlier passes forward.
- To use less memory. :: Unrelated.
- Because radix sort is a comparison sort. :: It is not.
- It does not need to be. :: It does.