⏱ 3 min read

🧮 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

Overview & Keywords
Must-Know Sorting Algorithms
Templates
Key Patterns
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

Pattern	Stable	Adaptive	In-place	Used In
Selection Sort	❌	❌	✅	Teaching
Bubble Sort	✅	✅	✅	Teaching
Insertion Sort	✅	✅	✅	TimSort, STL
Merge Sort	✅	❌	❌	stable_sort(), Linked
Quick Sort	❌	❌	✅	STL sort(), Introsort
Heap Sort	❌	❌	✅	Priority Queue
Counting Sort	✅	❌	✅	Bucket/Dutch Flag
Bucket Sort	✅	❌	✅	Max Gap, Floats
Radix Sort	✅	❌	✅	Phone Numbers, Strings