Sorting Algorithms
Sorting arranges elements in order. It’s the most studied problem in CS because it’s foundational — many algorithms require sorted input, and sorting reveals deep ideas about complexity.
Why It Matters
Sorted data enables Binary Search (O(log n)), simplifies deduplication, and is required for merge operations. Knowing which sort to use and why is practical engineering knowledge.
Comparison
| Algorithm | Time (avg) | Time (worst) | Space | Stable | Notes |
|---|---|---|---|---|---|
| Bubble sort | O(n^2) | O(n^2) | O(1) | Yes | Teaching only |
| Insertion sort | O(n^2) | O(n^2) | O(1) | Yes | Fast on small/nearly sorted |
| Merge sort | O(n log n) | O(n log n) | O(n) | Yes | Guaranteed performance |
| Quick sort | O(n log n) | O(n^2) | O(log n) | No | Fastest in practice |
| Heap sort | O(n log n) | O(n log n) | O(1) | No | In-place, not cache-friendly |
| Counting sort | O(n + k) | O(n + k) | O(k) | Yes | Only for integers, k = range |
Stable means equal elements keep their original relative order.
Merge Sort
Divide the array in half, recursively sort each half, then merge. Always O(n log n).
def merge_sort(arr: list) -> list:
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return _merge(left, right)
def _merge(a: list, b: list) -> list:
result = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:])
result.extend(b[j:])
return result
assert merge_sort([38, 27, 43, 3, 9, 82, 10]) == [3, 9, 10, 27, 38, 43, 82]Quick Sort
Pick a pivot, partition elements into less-than and greater-than, recurse. O(n log n) average, O(n^2) worst case (rare with random pivot).
import random
def quick_sort(arr: list) -> list:
if len(arr) <= 1:
return arr
pivot = arr[random.randint(0, len(arr) - 1)]
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
assert quick_sort([38, 27, 43, 3, 9, 82, 10]) == [3, 9, 10, 27, 38, 43, 82]When to Use What
- Default: use your language’s built-in sort (Python: Timsort, O(n log n), stable)
- Guaranteed O(n log n): merge sort
- In-place needed: quick sort or heap sort
- Small arrays / nearly sorted: insertion sort
- Integer keys with small range: counting sort
Related
- Big O Notation — complexity analysis
- Recursion — merge sort and quick sort are recursive
- Binary Search — requires sorted input
- Heaps — heap sort
- Arrays — sorting operates on arrays