🔒 Private Site

This site is password-protected.

Calculusphile Logo
calculusphile

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:

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

  1. Complexity:

    • Time: O(N²)

    • Space: O(1)

  2. Not Stable
    • Relative order not preserve.
    • Can be made stable by shifting elements instead of swapping, but it increases cost.
  3. Not Adaptive
    • Doesn’t take advantage of existing order of input.
  4. 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.

  1. Complexity

    • Time: O(N²)

    • Space: O(1)

  2. Space: O(1)

  3. Stable: ✅ Yes

  4. Adaptive: ✅ Yes (with optimization)

  5. 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

👉 Insertion Sort Code

  1. Complexity
    • Time: O(N²)
    • Space: O(1)
    • Best case O(N) when array is nearly sorted
  2. Internally used in:
    • TimSort
    • Hybrid sorts in C++ STL

  3. Stable: ✅ Yes

  4. Adaptive: ✅ Yes

  5. 👉 Conceptually important.

  6. 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:

Why?

To guarantee:

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

  1. Start with Quick Sort

    • Very fast due to cache locality

  2. If recursion depth > 2 × log₂(n)

    • Switch to Heap Sort

  3. 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)

🔹 High-Level Steps

👉 Merge Sort Code

  1. Used in:

    • stable_sort() in C++

    • Sorting linked lists

    • Counting inversions

  2. ⏱ 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

  3. Space Complexity

    • Extra array: O(n)

    • Recursion stack: O(log n)

    • 👉 Overall: O(n)

  4. Stability, In-Place, Adaptive

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

📌 You MUST know:

📌 Interview problems that use Merge Sort technique:

🔹 Why Merge Sort Is Preferred for Linked Lists

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

🔹 Interview Problems Based on Merge Sort

🔥 MUST-DO

  1. Merge two sorted arrays

  2. Merge sorted linked lists

  3. Count inversions in array

  4. Sort linked list

  5. Count smaller elements after self

🔥 HARD (Advanced)

  1. Reverse pairs

  2. Range sum count

  3. Skyline problem

🔶 5. Quick Sort (VERY IMPORTANT)

The most commonly asked theoretical sorting algorithm.

📌 You must know:

🔶 6. Heap Sort

Used indirectly in:

🔶 7. Counting Sort

Used in:

🔶 8. Bucket Sort

Used in:

🔶 9. Radix Sort

Used in:

Sorting in C++ (VERY IMPORTANT for interviews)

C++ STL sorts you must know

  1. sort() → IntroSort (Quick + Heap + Insertion) Time: O(N log N)

  2. stable_sort() → Merge Sort

  3. partial_sort()

  4. nth_element() → QuickSelect (VERY IMPORTANT)

❗ Interviewers often ask:

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)

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

Meeting rooms II

Level 2 (Medium)

  1. Leetcode 148. Sort List - My Approach & Leetcode Solution link

  2. Leetcode 179. Largest Number - My Approach & Leetcode Solution link

  3. Leetcode 75. Sort Colors - My Approach & Leetcode Solution link - Dutch National Flag Algorithm

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