🧮 Sorting Algorithms Master Guide

Sorting is a foundational topic in computer science and interviews. Mastering sorting means understanding the intuition, implementation, and use-cases for each algorithm.

📑 Table of Contents

1. Overview & Keywords
2. Must-Know Sorting Algorithms
3. Templates
4. Key Patterns
5. Practice Problems

Overview & Keywords

Sorting is the process of arranging data in a particular order (ascending/descending). Common interview keywords:

• stable
• adaptive
• in-place
• time/space complexity
• custom comparator
• hybrid sort

Must-Know Sorting Algorithms

🔶 Selection Sort

• Simple, conceptual warmup
• Time: O(N²), Space: O(1)
• Not stable, not adaptive
• Rarely used except for teaching

🔶 Bubble Sort

• Swap adjacent elements until sorted
• Time: O(N²), Space: O(1)
• Stable, adaptive (with optimization)
• Rarely used in practice

🔶 Insertion Sort

• Insert each element into its correct position
• Time: O(N²), Space: O(1), Best: O(N) for nearly sorted
• Stable, adaptive
• Used in TimSort, C++ STL hybrid sorts

🔶 Merge Sort

• Divide & conquer, merge sorted halves
• Time: O(N log N), Space: O(N)
• Stable, not in-place
• Used in stable_sort(), linked lists

🔶 Quick Sort

• Partition, recursively sort
• Time: Avg O(N log N), Worst O(N²)
• In-place, not stable
• Used in C++ STL sort() (as part of Introsort)

🔶 Heap Sort

• Build heap, extract max/min
• Time: O(N log N), Space: O(1)
• Not stable
• Used in priority queue, top-K problems

🔶 Counting Sort

• For small, bounded integer ranges
• Time: O(N + K), Space: O(K)
• Not comparison-based

🔶 Bucket Sort

• For uniformly distributed input
• Used in max gap, sorting floats

🔶 Radix Sort

• For integers/strings
• Time: O(d * (N + K))
• Used in phone number sorting, large datasets

Templates

Selection Sort

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        swap(arr[i], arr[minIndex]);
    }
}

Merge Sort

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid+1, r);
    merge(arr, l, mid, r);
}

Quick Sort (Lomuto)

int partition(vector<int>& a, int l, int r) {
    int pivot = a[r];
    int i = l;
    for (int j = l; j < r; j++) {
        if (a[j] < pivot) {
            swap(a[i], a[j]);
            i++;
        }
    }
    swap(a[i], a[r]);
    return i;
}

Key Patterns

Practice Problems

Level 1 — Basics

Level 2 — Medium

Level 3 — Hard