Chapter 12 — Sorting Algorithms
Chapter 12 — Sorting Algorithms
Hey everyone! Welcome back to Namaste DSA!
"Sort it first" is the hidden first step of a huge number of problems. In this chapter we go from the simple O(n²) sorts (great for learning the mechanics) to the O(n log n) champions merge sort and quick sort — and we'll understand exactly where that log n comes from.
What we will cover:
- Bubble, Selection, Insertion — the O(n²) trio
- Merge Sort — divide & conquer, stable
- Quick Sort — partitioning
- Why O(n log n) is the comparison-sort speed limit
- Counting Sort — beating n log n
- Stable vs unstable
- Interview Questions
1. The O(n²) Trio
| Sort | Idea | Best | Worst |
|---|---|---|---|
| Bubble | Swap adjacent out-of-order pairs; biggest "bubbles" to the end | O(n) | O(n²) |
| Selection | Find the min, put it at front; repeat | O(n²) | O(n²) |
| Insertion | Insert each item into its sorted-so-far place | O(n) | O(n²) |
// Insertion sort — great for nearly-sorted / small arrays
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i], j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]; // shift right
j--;
}
arr[j + 1] = key; // drop key in place
}
return arr;
}
BUBBLE SORT, one pass on [5, 2, 4, 1]: 5>2 swap → [2,5,4,1] 5>4 swap → [2,4,5,1] 5>1 swap → [2,4,1,5] ← 5 bubbled to the end (repeat passes until no swaps)
2. Merge Sort — Divide & Conquer
Split the array in half, sort each half (recursively), then merge the two sorted halves. The splitting gives log n levels; merging each level costs n — hence O(n log n).
[5, 2, 4, 1, 3]
/ \ ← log n levels of splitting
[5, 2] [4, 1, 3]
/ \ / \
[5] [2] [4] [1,3]
\ / \ / \
[2,5] [4] [1] [3]
\ \ \ /
\ \ [1,3]
\ \ /
\ [1,3,4]
\ /
[1, 2, 3, 4, 5] ← merge back up (n per level)
function mergeSort(arr) {
if (arr.length <= 1) return arr; // base case
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(a, b) {
const res = []; let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) res.push(a[i++]);
else res.push(b[j++]);
}
return res.concat(a.slice(i)).concat(b.slice(j));
}
Merge sort is stable (equal elements keep their order) and always O(n log n), but uses O(n) extra space.
3. Quick Sort — Partitioning
Pick a pivot, partition the array so smaller elements go left and bigger go right, then recurse on each side. Average O(n log n), but worst case O(n²) (a bad pivot on already-sorted data).
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo < hi) {
const p = partition(arr, lo, hi);
quickSort(arr, lo, p - 1);
quickSort(arr, p + 1, hi);
}
return arr;
}
function partition(arr, lo, hi) {
const pivot = arr[hi]; // last element as pivot
let i = lo - 1;
for (let j = lo; j < hi; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]]; // pivot into place
return i + 1;
}
4. Why O(n log n) is the Speed Limit
┌─────────────────────────────────────────────────────────────┐ │ Any COMPARISON-BASED sort needs at least O(n log n). │ │ │ │ There are n! possible orderings. Each comparison gives │ │ 1 bit of info (yes/no). You need log₂(n!) ≈ n log n │ │ comparisons to distinguish them all. You can't do better │ │ using only comparisons. │ └─────────────────────────────────────────────────────────────┘
5. Counting Sort — Beating n log n
If values are integers in a small known range, you can skip comparisons entirely. Count how many of each value, then write them out in order — O(n + k) where k is the range.
function countingSort(arr, maxVal) {
const count = new Array(maxVal + 1).fill(0);
for (const x of arr) count[x]++; // tally
const res = [];
for (let v = 0; v <= maxVal; v++)
while (count[v]-- > 0) res.push(v); // write out in order
return res;
}
This isn't magic — it works only because it exploits the small integer range (no comparisons), which is why it isn't bound by the n log n limit.
6. Stable vs Unstable
STABLE → equal elements keep their original relative order
(merge sort, counting sort, insertion sort)
UNSTABLE → equal elements may be reordered
(quick sort, selection sort, heap sort)
Matters when sorting by multiple keys
(e.g. sort by name, then keep that order while sorting by age).
Comparison Table
| Algorithm | Avg Time | Worst | Space | Stable? |
|---|---|---|---|---|
| Bubble | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n²) | O(log n) | No |
| Counting | O(n + k) | O(n + k) | O(k) | Yes |
Interview Questions — Quick Fire!
Q: Where does the log n in merge sort come from?
"From the splitting. Halving the array repeatedly gives about log₂(n) levels. At each level the merging touches all n elements, so total work is n × log n = O(n log n)."
Q: When is quick sort O(n²)?
"When the pivot is consistently the smallest or largest element — for example, picking the last element on an already-sorted array. Then partitions are maximally unbalanced. Randomizing the pivot or using median-of-three avoids this in practice."
Q: Why can't comparison sorts beat O(n log n)?
"There are n! possible orderings, and each comparison yields one bit of information. Distinguishing all orderings requires at least log₂(n!) ≈ n log n comparisons. Non-comparison sorts like counting sort can be faster because they exploit value structure instead of comparing."
Q: What does it mean for a sort to be stable?
"Equal elements keep their original relative order after sorting. It matters when sorting by a secondary key — a stable sort on the second key preserves the first key's ordering. Merge sort is stable; quick sort and heap sort are not."
Q: Merge sort vs quick sort — which would you choose?
"Quick sort is usually faster in practice with O(log n) space and good cache behaviour, so it's the default for in-memory arrays. Merge sort guarantees O(n log n), is stable, and works well for linked lists and external sorting, at the cost of O(n) extra space."
Quick Recap
| Concept | Key Takeaway |
|---|---|
| O(n²) trio | Bubble/selection/insertion — learn, rarely use. |
| Merge sort | Divide & conquer, stable, O(n log n), O(n) space. |
| Quick sort | Partition; avg O(n log n), worst O(n²). |
| Speed limit | Comparison sorts ≥ O(n log n). |
| Counting sort | O(n+k) for small integer ranges. |
| Stability | Keep equal elements' original order. |
What's Next?
Chapter 13: Searching Patterns — a short, practical wrap-up of Season 3 on choosing the right tool: linear vs binary, sort-first, or hash.
Keep coding, keep grinding! See you in the next one!
Post a Comment