Sorting Algorithms — Complete Guide with Visual Traces

Why Sorting Algorithms Matter

Sorting is the foundation of algorithm design. Once a collection is sorted, you unlock O(log N) binary search, O(N) two-pointer techniques, and efficient duplicate detection. Almost every real-world system — search engines, databases, operating systems, e-commerce — relies on sorting millions of records daily.

Understanding sorting algorithms also teaches you fundamental concepts: divide and conquer (Merge Sort), partitioning (Quick Sort), heap properties (Heap Sort), and incremental construction (Insertion Sort).

Sorting Algorithms Comparison Table

Stable sort: equal elements maintain their original relative order.
In-place sort: uses O(1) extra space (ignoring the input).

When to Use Which Sort?

Algorithm 1: Bubble Sort

Idea: Repeatedly swap adjacent elements that are in the wrong order. After each pass, the largest unsorted element "bubbles up" to its correct position.

Array: [5, 3, 8, 1, 2]

Pass 1:
[5,3,8,1,2] → swap(5,3) → [3,5,8,1,2]
[3,5,8,1,2] → 5<8, no swap
[3,5,8,1,2] → swap(8,1) → [3,5,1,8,2]
[3,5,1,8,2] → swap(8,2) → [3,5,1,2,8]   ← 8 is in place

Pass 2:
[3,5,1,2,8] → 3<5, no swap
[3,5,1,2,8] → swap(5,1) → [3,1,5,2,8]
[3,1,5,2,8] → swap(5,2) → [3,1,2,5,8]   ← 5 is in place

... continue until sorted: [1,2,3,5,8]

javascript
function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        let swapped = false;
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        if (!swapped) break;  // early exit if already sorted → O(N) best case
    }
    return arr;
}

console.log(bubbleSort([5, 3, 8, 1, 2]));  // [1, 2, 3, 5, 8]

Time: O(N²) average/worst, O(N) best (already sorted with early exit)
Use Bubble Sort when: Only for learning purposes. Never use in production due to O(N²) average case.

Algorithm 2: Insertion Sort

Idea: Build a sorted subarray on the left, one element at a time. For each new element, insert it into its correct position by shifting larger elements right.

Array: [5, 3, 8, 1, 2]

Start: [5] | 3, 8, 1, 2

Insert 3: 3 < 5, shift 5 right → [3, 5] | 8, 1, 2
Insert 8: 8 > 5, no shift     → [3, 5, 8] | 1, 2
Insert 1: 1 < 8 → shift 8
          1 < 5 → shift 5
          1 < 3 → shift 3
          → [1, 3, 5, 8] | 2
Insert 2: 2 < 8 → shift, 2 < 5 → shift, 2 < 3 → shift, 2 > 1 → insert
          → [1, 2, 3, 5, 8]

javascript
function insertionSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        const key = arr[i];
        let j = i - 1;
        // Shift all elements greater than key one position to the right
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;  // insert key at its correct position
    }
    return arr;
}

console.log(insertionSort([5, 3, 8, 1, 2]));  // [1, 2, 3, 5, 8]

Time: O(N²) average/worst, O(N) best (nearly sorted)
Use Insertion Sort when: Array is small (< 20 elements) or nearly sorted. Java's Arrays.sort() uses Timsort which applies Insertion Sort for small subarrays.

Algorithm 3: Merge Sort ⭐ (Most Important for Interviews)

Idea: Divide the array in half, recursively sort each half, then merge the two sorted halves. Classic divide and conquer.

Array: [5, 3, 8, 1, 2]

Split:
    [5, 3, 8, 1, 2]
    /               \
[5, 3, 8]         [1, 2]
  /    \           /   \
[5, 3] [8]      [1]   [2]
 /   \
[5] [3]

Merge (bottom up):
[5] + [3] → [3, 5]
[3, 5] + [8] → [3, 5, 8]
[1] + [2] → [1, 2]
[3, 5, 8] + [1, 2] → [1, 2, 3, 5, 8] ✅

The Merge Step (key operation):

Merge [3, 5, 8] and [1, 2]:
  Compare 3 vs 1: 1 < 3 → take 1 → result [1], right pointer →
  Compare 3 vs 2: 2 < 3 → take 2 → result [1,2], right pointer → done
  Take remaining left: 3, 5, 8 → result [1,2,3,5,8] ✅

javascript
function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    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(left, right) {
    const result = [];
    let l = 0, r = 0;

    while (l < left.length && r < right.length) {
        if (left[l] <= right[r]) {
            result.push(left[l++]);
        } else {
            result.push(right[r++]);
        }
    }

    return [...result, ...left.slice(l), ...right.slice(r)];
}

console.log(mergeSort([5, 3, 8, 1, 2]));  // [1, 2, 3, 5, 8]

Python:

python
def merge_sort(arr):
    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(left, right):
    result = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] <= right[r]:
            result.append(left[l]); l += 1
        else:
            result.append(right[r]); r += 1
    return result + left[l:] + right[r:]

Time: O(N log N) always — guaranteed
Space: O(N) — extra arrays for merging
Use Merge Sort when: You need a stable, guaranteed O(N log N) sort, or sorting linked lists (no random access needed).

Algorithm 4: Quick Sort ⭐ (Fastest in Practice)

Idea: Choose a pivot element, partition the array so all elements smaller than pivot come before it and all larger elements come after it. Recursively sort the two partitions.

Array: [5, 3, 8, 1, 2], pivot = 5 (last element strategy)

Partition step:
  Left pointer scans right, looking for element ≥ pivot
  Right pointer scans left, looking for element ≤ pivot

Using Lomuto partition (pivot = last element):
  pivot = 2
  [5, 3, 8, 1 | 2]
  i=-1, scan j from 0:
  j=0: arr[0]=5 > 2, skip
  j=1: arr[1]=3 > 2, skip
  j=2: arr[2]=8 > 2, skip
  j=3: arr[3]=1 ≤ 2, i++, swap(arr[0], arr[3]) → [1, 3, 8, 5 | 2]
  End: i=0, swap(arr[i+1], pivot) → [1, 2, 8, 5, 3]
  Pivot 2 is at index 1 — correct position!

Recurse on [1] and [8, 5, 3]...

javascript
function quickSort(arr, low = 0, high = arr.length - 1) {
    if (low < high) {
        const pivotIdx = partition(arr, low, high);
        quickSort(arr, low, pivotIdx - 1);
        quickSort(arr, pivotIdx + 1, high);
    }
    return arr;
}

function partition(arr, low, high) {
    const pivot = arr[high];  // Lomuto: choose last element as pivot
    let i = low - 1;

    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

console.log(quickSort([5, 3, 8, 1, 2]));  // [1, 2, 3, 5, 8]

Random Pivot (Avoids O(N²) Worst Case):

javascript
function partition(arr, low, high) {
    // Randomize pivot to avoid worst case on sorted arrays
    const randomIdx = low + Math.floor(Math.random() * (high - low + 1));
    [arr[randomIdx], arr[high]] = [arr[high], arr[randomIdx]];
    // ... rest of Lomuto partition
}

Time: O(N log N) average, O(N²) worst (sorted array with bad pivot)
Space: O(log N) — recursion stack
Use Quick Sort when: General purpose sorting with large datasets. JavaScript's Array.sort() and Python's list.sort() use Timsort (hybrid of Merge + Insertion), but Quick Sort is faster for most practical cases due to cache efficiency.

Algorithm 5: Heap Sort

Idea: Build a max-heap from the array, then repeatedly extract the maximum and place it at the end.

[4, 10, 3, 5, 1]

Build Max Heap:
        10
       /  \
      5    3
     / \
    4   1

Heap array: [10, 5, 3, 4, 1]

Extract max (10): swap with last, heapify → [5, 4, 3, 1, 10]
Extract max (5): swap with last, heapify → [4, 1, 3, 5, 10]
Extract max (4): → [3, 1, 4, 5, 10]
Extract max (3): → [1, 3, 4, 5, 10]
Result: [1, 3, 4, 5, 10] ✅

javascript
function heapSort(arr) {
    const n = arr.length;

    // Build max heap (heapify all non-leaf nodes bottom-up)
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract elements one by one
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];  // move current max to end
        heapify(arr, i, 0);                    // restore heap for remaining
    }

    return arr;
}

function heapify(arr, n, i) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);  // recursively heapify affected subtree
    }
}

console.log(heapSort([4, 10, 3, 5, 1]));  // [1, 3, 4, 5, 10]

Time: O(N log N) always — guaranteed, no bad pivot issues
Space: O(1) — in-place!
Use Heap Sort when: You need O(N log N) worst-case AND O(1) extra space (memory-constrained environments).

Counting Sort & Radix Sort (Non-Comparison Based)

Counting Sort — O(N + K)

When the range of values K is small (e.g., 0-100), counting sort beats O(N log N) comparison sorts.

javascript
function countingSort(arr, maxVal) {
    const count = new Array(maxVal + 1).fill(0);

    // Count occurrences
    for (const num of arr) count[num]++;

    // Reconstruct sorted array
    const result = [];
    for (let i = 0; i <= maxVal; i++) {
        while (count[i]-- > 0) result.push(i);
    }
    return result;
}

console.log(countingSort([4, 2, 2, 8, 3, 3, 1], 8));
// [1, 2, 2, 3, 3, 4, 8]

Radix Sort — O(NK) where K = number of digits

Sorts integers digit by digit from least significant to most significant.

javascript
function radixSort(arr) {
    const maxVal = Math.max(...arr);
    for (let exp = 1; Math.floor(maxVal / exp) > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
    return arr;
}

function countingSortByDigit(arr, exp) {
    const n = arr.length;
    const output = new Array(n);
    const count = new Array(10).fill(0);

    for (let i = 0; i < n; i++) count[Math.floor(arr[i] / exp) % 10]++;
    for (let i = 1; i < 10; i++) count[i] += count[i - 1];
    for (let i = n - 1; i >= 0; i--) {
        const digit = Math.floor(arr[i] / exp) % 10;
        output[--count[digit]] = arr[i];
    }
    for (let i = 0; i < n; i++) arr[i] = output[i];
}

Common Sorting Interview Problems

Sort Colors (Dutch National Flag) 🟡

Problem: Given an array with values 0, 1, 2 (representing red, white, blue), sort them in-place.

javascript
function sortColors(nums) {
    let low = 0, mid = 0, high = nums.length - 1;

    while (mid <= high) {
        if (nums[mid] === 0) {
            [nums[low], nums[mid]] = [nums[mid], nums[low]];
            low++; mid++;
        } else if (nums[mid] === 1) {
            mid++;
        } else {
            [nums[mid], nums[high]] = [nums[high], nums[mid]];
            high--;
        }
    }
}

const arr = [2, 0, 2, 1, 1, 0];
sortColors(arr);
console.log(arr); // [0, 0, 1, 1, 2, 2]

Time: O(N) Space: O(1) — this is a variant of Quick Sort's 3-way partition!

Common Mistakes in Sorting

1. Using Bubble Sort in interviews: It signals unfamiliarity with better algorithms. Always mention Merge Sort or Quick Sort unless specifically asked for Bubble Sort.

2. Quick Sort worst case on sorted input: Always randomize the pivot in real implementations. Sorted arrays cause O(N²) with last/first-element pivot selection.

3. Stability confusion: Using Quick Sort or Heap Sort when you need to preserve relative order of equal elements. Merge Sort and Insertion Sort are stable; Quick Sort and Heap Sort are not.

4. Counting Sort with large ranges: Counting Sort is only efficient when the value range K is O(N). For large ranges (e.g., sorting 32-bit integers), it wastes O(2³²) memory — use Radix Sort or comparison-based sorts instead.

Frequently Asked Questions

Q: Which sorting algorithm does Java/Python/JavaScript use internally?
A: Python's list.sort() and Java's Arrays.sort() for objects use Timsort — a hybrid of Merge Sort and Insertion Sort that exploits naturally occurring runs in the data. Java's Arrays.sort() for primitives uses Dual-Pivot Quick Sort. JavaScript's Array.sort() is implementation-dependent but V8 uses Timsort since 2019.

Q: Can you sort in O(N)? Isn't O(N log N) the limit?
A: O(N log N) is the lower bound for comparison-based sorting (proven by decision tree argument). But non-comparison sorts (Counting Sort, Radix Sort) can achieve O(N) by exploiting the structure of the data (limited range, fixed-length keys). These aren't universally applicable — they work only for specific data types.

Q: Why is Quick Sort faster than Merge Sort in practice despite same complexity?
A: Quick Sort is cache-friendly — it works in-place, accessing memory sequentially during partitioning. Merge Sort requires allocating new arrays for merging, causing cache misses. Quick Sort's constant factor is smaller. However, Merge Sort has better worst-case guarantees and is preferred when stability matters.

Q: What is the space complexity of recursive Merge Sort vs. iterative?
A: Recursive Merge Sort: O(N) for the merge buffer + O(log N) for the call stack = O(N) total. Iterative (bottom-up) Merge Sort eliminates the call stack overhead but still needs O(N) for the merge buffer. Both are O(N) in practice.