⏱ 6 min read

Sorting Master Guide (Interview-Focused)

Sorting Algorithms You MUST Know (Interview Level)

Sorting an Array using Recursion

🔶 1. Selection Sort (Basic)

🔹 Intuition

Selection Sort works on a very simple idea:

Repeatedly select the minimum element from the unsorted part and place it at the correct position in the sorted part.

Think of it like:

You scan the entire array
Pick the smallest element
Put it at the beginning
Shrink the unsorted region
Repeat

🔹 C++ Implementation

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]);
    }
}

Complexity:
- Time: O(N²)
- Space: O(1)
Not Stable
- Relative order not preserve.
- Can be made stable by shifting elements instead of swapping, but it increases cost.
Not Adaptive
- Doesn’t take advantage of existing order of input.
Not used in interviews except conceptual warmup

For more on Stable and Adaptive sorting CLICK HERE

🔶 2. Bubble Sort

🔹 Intuition

Keep swapping adjacent elements if they are in the wrong order until the largest element bubbles to the end.

Largest elements bubble up to the right in each pass.

Complexity
- Time: O(N²)
- Space: O(1)
Space: O(1)
Stable: ✅ Yes
Adaptive: ✅ Yes (with optimization)
Again, basic; rarely asked.

🔹 Optimized Bubble Sort (IMPORTANT)

If no swaps occur in a pass, array is already sorted → stop early.

👉 Bubble Sort Code

🔶 3. Insertion Sort

🔹 Intuition

Take the next element and insert it into its correct position in the already sorted part.

Exactly how you sort playing cards in hand.

🔹 Algorithm Steps

Assume first element is sorted
Pick next element (key)
Shift larger elements one step right
Insert key at correct position
Repeat

👉 Insertion Sort Code

Complexity
- Time: O(N²)
- Space: O(1)
- Best case O(N) when array is nearly sorted
Internally used in:
- TimSort
- Hybrid sorts in C++ STL
Stable: ✅ Yes
Adaptive: ✅ Yes
👉 Conceptually important.
Used inside:
- C++ STL sort()
- Java / Python TimSort

Insertion sort is preferred over bubble sort because it performs fewer swaps and is significantly faster on nearly sorted data.

🔥 Which Sorting Algorithm Is Used in C++ STL sort()?

C++ STL sort() uses Introsort, a hybrid algorithm combining Quick Sort, Heap Sort, and Insertion Sort.

What Is Introsort? (Deep but Clear)

Introsort (Introspective Sort) starts like Quick Sort, but:

Monitors recursion depth
If recursion goes too deep (risk of O(n²)), → switches to Heap Sort
For small subarrays, it uses Insertion Sort

Why?

To guarantee:

Average case: O(n log n)
Worst case: O(n log n) (Quick Sort alone can degrade)
High practical performance

STL sort() Strategy (Step-by-Step)

Start with Quick Sort
- Very fast due to cache locality
If recursion depth > 2 × log₂(n)
- Switch to Heap Sort
If subarray size ≤ 16 (or small constant)
- Use Insertion Sort

📌 If you need stability, use:

stable_sort()

which uses Merge Sort.

🧪 Interview Trap Question

Q: Is std::sort() stable? ❌ No

Q: Why not use merge sort always? ✅ Extra memory + slower in practice due to cache misses.

🔶 4. Merge Sort (VERY IMPORTANT)

🔹 Intuition (Say This in Interviews)

Merge Sort uses Divide & Conquer:
Divide the array into halves until single elements remain, then merge them back in sorted order.

🔹 High-Level Steps

Divide array into two halves
Recursively sort both halves
Merge two sorted halves

👉 Merge Sort Code

Used in:
- stable_sort() in C++
- Sorting linked lists
- Counting inversions
⏱ Time Complexity
- Best: O(n log n)
- Average: O(n log n)
- Worst: O(n log n)
- Depth of recursion tree: log n
- Work at each level: n
Space Complexity
- Extra array: O(n)
- Recursion stack: O(log n)
- 👉 Overall: O(n)
Stability, In-Place, Adaptive

Property	Merge Sort
Stable	✅ Yes
In-place	❌ No
Adaptive	❌ No

📌 You MUST know:

How merge works
Recursion tree
Space complexity reasoning

📌 Interview problems that use Merge Sort technique:

Count inversions in array
Sort linked list
Merge k sorted lists
Count smaller elements after self

🔹 Why Merge Sort Is Preferred for Linked Lists

👉 Arrays need extra space for merging 👉 Linked lists can merge by changing pointers

✔ No extra array
✔ Truly O(1) extra space
✔ Still stable

🔹 Interview Problems Based on Merge Sort

🔥 MUST-DO

Merge two sorted arrays
Merge sorted linked lists
Count inversions in array
Sort linked list
Count smaller elements after self

🔥 HARD (Advanced)

Reverse pairs
Range sum count
Skyline problem

🔶 5. Quick Sort (VERY IMPORTANT)

The most commonly asked theoretical sorting algorithm.

Average: O(N log N)
Worst case: O(N²)
In-place
Not stable

📌 You must know:

Partitioning (Lomuto/Hoare)
Recursion depth
Randomized quick sort (expected O(N log N))
Why it’s used in practice (cache-friendly)

🔶 6. Heap Sort

Time: O(N log N)
Space: O(1)
Not stable

Used indirectly in:

Top-K problems
Priority queue interview questions

🔶 7. Counting Sort

Time: O(N + K)
Space: O(K)
Only for small, bounded integer ranges

Used in:

Sorting colors (Dutch National Flag)
Bucket-based questions

🔶 8. Bucket Sort

Used when input is uniformly distributed.

Used in:

Maximum gap problem
Sorting decimals/floats
LeetCode “Min Time to Make Rope Colorful” type problems indirectly

🔶 9. Radix Sort

Time: O(d * (N + K))
Works for integers and strings (ASCII-wide)

Used in:

Phone number sorting
Large dataset / distributed systems

Sorting in C++ (VERY IMPORTANT for interviews)

C++ STL sorts you must know

sort() → IntroSort (Quick + Heap + Insertion) Time: O(N log N)
stable_sort() → Merge Sort
partial_sort()
nth_element() → QuickSelect (VERY IMPORTANT)

❗ Interviewers often ask:

How does sort() work internally?
Is C++ sort stable? (Answer: No)
Why use stable_sort()?
How to sort using custom comparator?

Coding Templates You Must Know

🔹 Merge Sort (Template)

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 Partition)

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;
}

MUST DO PROBLEMS

Level 1 (Basic)

Leetcode 88. Merge Sorted Array - My Approach & Leetcode Solution link

Meeting rooms II

Level 2 (Medium)

K closest points

Minimum arrows to burst balloons

Group anagrams

Reduce array size to half (bucket sort)

Level 3 (Hard)

Count inversions

Maximum gap

Merge k sorted lists

Count smaller elements after self

Skyline problem