16 Sorting Algorithms
17 Sorting Algorithms
Week 7, Session 2. CSS 342.
17.1 Warmup
Sort Colors (#75). Given nums of 0s, 1s, and 2s, sort in place — without using a sort function.
class Solution {
public:
void sortColors(vector<int>& nums) {
int lo = 0, mid = 0, hi = nums.size() - 1;
while (mid <= hi) {
if (nums[mid] == 0) swap(nums[lo++], nums[mid++]);
else if (nums[mid] == 2) swap(nums[mid], nums[hi--]);
else ++mid;
}
}
};That is the Dutch National Flag three-way partition. O(n) one pass, O(1) extra space. Beautiful.
17.2 Learning objectives
- Implement bubble sort, selection sort, and insertion sort and state their complexities.
- Implement merge sort recursively and derive its O(n log n) complexity.
- Compare sorting algorithms on time complexity, space complexity, stability, and practical performance.
- Trace through each algorithm on a 6-element array.
- Explain why no comparison-based sort can beat O(n log n) in the worst case.
17.3 Bubble sort — O(n²)
Repeatedly pass through the array, swapping adjacent out-of-order pairs.
void bubbleSort(vector<int>& v) {
int n = v.size();
for (int i = 0; i < n - 1; ++i) {
bool swapped = false;
for (int j = 0; j < n - i - 1; ++j) {
if (v[j] > v[j + 1]) {
swap(v[j], v[j + 1]);
swapped = true;
}
}
if (!swapped) return; // early exit if already sorted
}
}After i outer iterations, the last i elements are in their final position. The early-exit swapped flag gives O(n) best case on an already-sorted input.
17.4 Selection sort — always O(n²)
Find the minimum, swap to front. Find the next-smallest, swap to position 1. Repeat.
void selectionSort(vector<int>& v) {
int n = v.size();
for (int i = 0; i < n - 1; ++i) {
int minIdx = i;
for (int j = i + 1; j < n; ++j) {
if (v[j] < v[minIdx]) minIdx = j;
}
swap(v[i], v[minIdx]);
}
}Always Θ(n²) — no early exit possible because every minimum-finding pass scans the whole remainder.
17.5 Insertion sort — O(n²) worst, O(n) best
Build sorted order one element at a time.
void insertionSort(vector<int>& v) {
for (int i = 1; i < (int)v.size(); ++i) {
int key = v[i];
int j = i - 1;
while (j >= 0 && v[j] > key) {
v[j + 1] = v[j];
--j;
}
v[j + 1] = key;
}
}On already-sorted input, the inner while never executes. Best case: O(n). For nearly sorted input, insertion sort is shockingly fast — better than O(n log n) in practice. That is why std::sort falls back to insertion sort for small subarrays.
17.6 Merge sort — O(n log n) guaranteed
Divide in half, sort each half, merge.
void merge(vector<int>& v, int lo, int mid, int hi) {
vector<int> tmp;
tmp.reserve(hi - lo + 1);
int i = lo, j = mid + 1;
while (i <= mid && j <= hi) {
if (v[i] <= v[j]) tmp.push_back(v[i++]);
else tmp.push_back(v[j++]);
}
while (i <= mid) tmp.push_back(v[i++]);
while (j <= hi) tmp.push_back(v[j++]);
for (int k = 0; k < (int)tmp.size(); ++k) v[lo + k] = tmp[k];
}
void mergeSort(vector<int>& v, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
mergeSort(v, lo, mid);
mergeSort(v, mid + 1, hi);
merge(v, lo, mid, hi);
}17.6.1 Why O(n log n)?
The recurrence is T(n) = 2T(n/2) + O(n).
- Two recursive calls on inputs of size n/2.
- The merge step is O(n).
Drawing the recursion tree: log n levels, O(n) work per level, total O(n log n).
n ← O(n) work
/ \
n/2 n/2 ← 2 × O(n/2) = O(n) work
/ \ / \
n/4 n/4 n/4 n/4 ← 4 × O(n/4) = O(n) work
...
(log n levels)Total work: n × log n.
Merge sort’s space cost is O(n) — the temporary buffer. That is why std::sort uses introsort (quicksort) — it sorts in place, at the cost of an O(n²) worst case that introsort prevents by switching to heapsort.
17.7 Quicksort — O(n log n) average, O(n²) worst
We will not implement quicksort in full here (343 covers it more deeply). The idea: pick a pivot, partition the array so smaller elements go left and larger go right, recurse on each side.
- Average case (random pivot): O(n log n).
- Worst case (pivot is always min or max): O(n²).
In practice, quicksort with a randomized pivot or median-of-three is faster than merge sort. That is what std::sort uses.
17.8 Comparison table
| Algorithm | Best | Average | Worst | Space | Stable | In place |
|---|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
Stable = preserves order of equal elements. Matters when sorting by a secondary key.
17.9 The Ω(n log n) lower bound
Any comparison-based sort makes a sequence of pairwise comparisons. Each comparison gives one bit of information. There are n! possible orderings of n elements. To distinguish them you need at least log₂(n!) ≈ n log n bits. So no comparison sort can beat O(n log n) in the worst case.
(Non-comparison sorts like radix sort can beat it — they exploit the structure of the keys.)
17.10 Try it
Implement insertion sort. Add a print statement at the start of each outer iteration so you can watch it work. Then sort {5, 2, 8, 1, 9, 3} and trace the output.
Now sort {1, 2, 3, 4, 5} (already sorted). Confirm the inner while never executes. That is the O(n) best case.
17.11 Self-check
17.12 Challenges
- Implement merge sort. Verify on random arrays.
- Merge Two Sorted Lists (#21) — the merge step on linked lists.
- Sort an Array (#912) — implement merge sort or quicksort.
17.13 Where this fits
Sorting is the worked example for big-O. The next chapter — induction — provides the formal machinery for proving that recursive algorithms (like merge sort) actually work.
| You are here | Coming up |
|---|---|
| Bubble, selection, insertion, merge, comparison table | Chapter 15: mathematical induction |