Sorting Algorithms (Bubble, Selection, Insertion, Merge, Quick)

0/14 in this phase0/57 across the roadmap

📖 Concept

Sorting is the most fundamental algorithm category. Understanding sorting teaches you divide & conquer, recursion, time-space tradeoffs, and stability.

The Big Five:

Algorithm	Time (Best)	Time (Avg)	Time (Worst)	Space	Stable?
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	✅
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	❌
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	✅
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌

When to use each:

Insertion Sort: Small arrays, nearly sorted data, online sorting (TimSort uses it!)
Merge Sort: Need guaranteed O(n log n), need stability, linked lists
Quick Sort: General purpose, best cache performance, in-place

Stability means equal elements keep their original relative order. Important when sorting by multiple criteria (sort by name, then by age — stable sort preserves name order for same ages).

Key insight: No comparison-based sort can do better than O(n log n). This is a proven lower bound. Non-comparison sorts (counting, radix, bucket) can achieve O(n) for special inputs.

🏠 Real-world analogy: Bubble sort is like repeatedly walking through a line and swapping people who are out of order. Merge sort is like splitting a deck of cards in half, sorting each half, then merging them back. Quick sort is like picking a pivot person and sending everyone shorter to the left, taller to the right.

💻 Code Example

codeTap to expand ⛶

1// BUBBLE SORT — O(n²), simple but slow
2function bubbleSort(arr: number[]): number[] {
3  const n = arr.length;
4  for (let i = 0; i < n - 1; i++) {
5    let swapped = false;
6    for (let j = 0; j < n - i - 1; j++) {
7      if (arr[j] > arr[j + 1]) {
8        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
9        swapped = true;
10      }
11    }
12    if (!swapped) break; // Optimization: already sorted
13  }
14  return arr;
15}
16
17// INSERTION SORT — O(n) best case for nearly sorted
18function insertionSort(arr: number[]): number[] {
19  for (let i = 1; i < arr.length; i++) {
20    const key = arr[i];
21    let j = i - 1;
22    while (j >= 0 && arr[j] > key) {
23      arr[j + 1] = arr[j];
24      j--;
25    }
26    arr[j + 1] = key;
27  }
28  return arr;
29}
30
31// MERGE SORT — O(n log n) guaranteed, stable
32function mergeSort(arr: number[]): number[] {
33  if (arr.length <= 1) return arr;
34  const mid = Math.floor(arr.length / 2);
35  const left = mergeSort(arr.slice(0, mid));
36  const right = mergeSort(arr.slice(mid));
37  return merge(left, right);
38}
39
40function merge(left: number[], right: number[]): number[] {
41  const result: number[] = [];
42  let i = 0, j = 0;
43  while (i < left.length && j < right.length) {
44    if (left[i] <= right[j]) result.push(left[i++]);
45    else result.push(right[j++]);
46  }
47  return [...result, ...left.slice(i), ...right.slice(j)];
48}
49
50// QUICK SORT — O(n log n) average, in-place
51function quickSort(arr: number[], lo = 0, hi = arr.length - 1): number[] {
52  if (lo < hi) {
53    const pivotIdx = partition(arr, lo, hi);
54    quickSort(arr, lo, pivotIdx - 1);
55    quickSort(arr, pivotIdx + 1, hi);
56  }
57  return arr;
58}
59
60function partition(arr: number[], lo: number, hi: number): number {
61  const pivot = arr[hi];
62  let i = lo;
63  for (let j = lo; j < hi; j++) {
64    if (arr[j] < pivot) {
65      [arr[i], arr[j]] = [arr[j], arr[i]];
66      i++;
67    }
68  }
69  [arr[i], arr[hi]] = [arr[hi], arr[i]];
70  return i;
71}
72
73// SELECTION SORT — O(n²), minimizes swaps
74function selectionSort(arr: number[]): number[] {
75  for (let i = 0; i < arr.length - 1; i++) {
76    let minIdx = i;
77    for (let j = i + 1; j < arr.length; j++) {
78      if (arr[j] < arr[minIdx]) minIdx = j;
79    }
80    if (minIdx !== i) [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
81  }
82  return arr;
83}

🏋️ Practice Exercise

Practice Problems:

Implement bubble sort with early termination optimization
Implement insertion sort and test on a nearly-sorted array
Implement merge sort and trace the recursive calls
Implement quick sort with the Lomuto partition scheme
Sort an array of 0s, 1s, and 2s in-place (Dutch National Flag)
Find the kth largest element using quick select (partial quick sort)
Merge k sorted arrays using merge sort approach
Sort a linked list using merge sort
Implement counting sort for integers in range [0, k]
Sort an array by frequency of elements

⚠️ Common Mistakes

Using bubble sort in production — it's O(n²); use the language's built-in sort (usually Timsort or Introsort)
Choosing quick sort without randomization — sorted input gives O(n²) with fixed pivot
Forgetting that merge sort needs O(n) extra space — important for space-constrained systems
Not understanding stability — can cause bugs when sorting objects by multiple fields
Implementing quick sort recursively on already-sorted large arrays — can cause stack overflow

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Sorting Algorithms (Bubble, Selection, Insertion, Merge, Quick)

Was this topic helpful?

← PreviousMatrices & 2D Arrays Next →Searching Algorithms (Linear & Binary Search)