Sorting: Organizing Chaos
Sorting is fundamental. Whether it's organizing files by date, contacts by name, or products by price, sorting is everywhere.
Comprehensive Sorting Comparison
| Algorithm | Best | Average | Worst | Space | Stable? | Method |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Comparison |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Comparison |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Comparison |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Divide & Conquer |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Divide & Conquer |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Comparison |
What is Stability in Sorting?
Stable Sort: Two elements with equal keys maintain their original relative order after sorting.
| Original | Stable Sort | Unstable Sort |
|---|---|---|
| (Alice, 85), (Bob, 85), (Carol, 90) | (Alice, 85), (Bob, 85), (Carol, 90) | (Bob, 85), (Alice, 85), (Carol, 90) |
When does stability matter? When sorting by multiple criteria (e.g., sort by name, then by grade — you want same-grade students to stay alphabetical).
1. Insertion Sort (The "Card Player" Method)
How it works: Pick elements one at a time and insert them into their correct position in the sorted portion.
Trace: Array: [5, 3, 4, 1, 2]
| Pass | Key | Action | Array |
|---|---|---|---|
| 1 | 3 | 3 < 5, shift 5 right | [3, 5, 4, 1, 2] |
| 2 | 4 | 4 < 5, shift; 4 > 3, insert | [3, 4, 5, 1, 2] |
| 3 | 1 | Shift 5, 4, 3 right | [1, 3, 4, 5, 2] |
| 4 | 2 | Shift 5, 4, 3 right; insert after 1 | [1, 2, 3, 4, 5] |
Best for: Small arrays, nearly sorted data. Worst for: Large unsorted arrays.
2. Selection Sort (The "Pick the Best" Method)
How it works: Find the minimum element and swap it with the first unsorted position.
Trace: Array: [64, 25, 12, 22]
| Pass | Min Found | Swap With | Result |
|---|---|---|---|
| 1 | 12 (index 2) | 64 (index 0) | [12, 25, 64, 22] |
| 2 | 22 (index 3) | 25 (index 1) | [12, 22, 64, 25] |
| 3 | 25 (index 3) | 64 (index 2) | [12, 22, 25, 64] |
Note: Always makes O(n²) comparisons regardless of input order.
3. Merge Sort (The "Divide & Conquer" Strategy)
How it works: Recursively split array in half until single elements, then merge sorted halves.
Trace: [38, 27, 43, 3]
[38, 27, 43, 3]
/ \
[38, 27] [43, 3]
/ \ / \
[38] [27] [43] [3]
\ / \ /
[27, 38] [3, 43]
\ /
[3, 27, 38, 43]Key Advantage: Always O(n log n). Disadvantage: Requires O(n) extra space.
4. Quick Sort (The "Pivot" Strategy)
How it works: Choose a pivot, partition array so elements < pivot go left, > pivot go right. Recurse on both halves.
Trace: [10, 7, 8, 9, 1, 5], Pivot = 5
- Partition: elements < 5 go left, > 5 go right →
[1, 5, 8, 9, 10, 7] - Recurse on
[1](done) and[8, 9, 10, 7] - Continue partitioning until sorted.
| Feature | Quick Sort | Merge Sort |
|---|---|---|
| Average | O(n log n) | O(n log n) |
| Worst | O(n²) (bad pivot) | O(n log n) |
| Space | O(log n) in-place | O(n) extra |
| Stable | No | Yes |
| In Practice | Faster (cache-friendly) | Used when stability needed |
Choosing the Right Sort
| Scenario | Best Algorithm | Why |
|---|---|---|
| Small array (< 50) | Insertion Sort | Low overhead, simple |
| Nearly sorted data | Insertion Sort | O(n) best case |
| Large dataset, guaranteed perf | Merge Sort | O(n log n) always |
| General purpose, in-place | Quick Sort | Fastest in practice |
| Memory constrained | Heap Sort | O(1) extra space |