🧮 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#

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

---

Practice Problems#

Level 1 — Basics#

Level 2 — Medium#

Level 3 — Hard#

---