All Sorting & Searching Algorithms

A comprehensive reference covering every major sorting and searching algorithm with deep intuition, step-by-step visuals, complexity analysis, and production-quality C++ code.

Sorting Overview Table
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Heap Sort
Counting Sort
Radix Sort
Bucket Sort
Quick Sort vs Merge Sort
C++ STL sort()
Linear Search
Binary Search
Ternary Search
Exponential Search
STL Search Functions
Binary Search Patterns for Interviews

SORTING ALGORITHMS

Sorting Overview Table

Terminology:

n = number of elements
k = range of input values (for counting/radix sort)
d = number of digits (for radix sort)
Stable = equal elements maintain their original relative order
In-place = uses O(1) extra space (ignoring recursion stack)

Imagine bubbles rising in water: the largest element "bubbles up" to the end of the array in each pass. We repeatedly walk through the array, comparing adjacent pairs and swapping them if they are in the wrong order. After each complete pass, the next-largest element is guaranteed to be in its final position.

Algorithm

For each pass i from 0 to n-2:
- Walk through indices j from 0 to n-2-i
- If arr[j] > arr[j+1], swap them
Optimization: If no swaps occurred in a pass, the array is sorted --- stop early.

Visual Step-by-Step

Input: [5, 3, 8, 1, 2]

Pass 1:
  [5, 3, 8, 1, 2]   compare 5,3 -> swap
  [3, 5, 8, 1, 2]   compare 5,8 -> ok
  [3, 5, 8, 1, 2]   compare 8,1 -> swap
  [3, 5, 1, 8, 2]   compare 8,2 -> swap
  [3, 5, 1, 2, 8]   8 is now in final position
                              ^

Pass 2:
  [3, 5, 1, 2, 8]   compare 3,5 -> ok
  [3, 5, 1, 2, 8]   compare 5,1 -> swap
  [3, 1, 5, 2, 8]   compare 5,2 -> swap
  [3, 1, 2, 5, 8]   5 is now in final position
                           ^

Pass 3:
  [3, 1, 2, 5, 8]   compare 3,1 -> swap
  [1, 3, 2, 5, 8]   compare 3,2 -> swap
  [1, 2, 3, 5, 8]   3 is now in final position
                        ^

Pass 4:
  [1, 2, 3, 5, 8]   compare 1,2 -> ok
  No swaps! -> Early termination.

Result: [1, 2, 3, 5, 8]

Complexity Analysis

Case	Time	Explanation
Best	O(n)	Already sorted; one pass with no swaps triggers early termination
Average	O(n^2)	Roughly n^2/4 swaps on average
Worst	O(n^2)	Reverse sorted; every pair needs swapping
Space	O(1)	Only a few temporary variables

C++ Code

CPP

#include <bits/stdc++.h>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;  // Early termination: already sorted
    }
}

When to Use

Almost never in practice. Bubble sort is primarily educational. Its only marginal advantage is detecting an already-sorted array in O(n), but insertion sort does the same thing and is faster on nearly-sorted data.

2. Selection Sort

Intuition

Divide the array into two regions: sorted (left) and unsorted (right). Repeatedly find the minimum element in the unsorted region and swap it into the first position of the unsorted region, thereby growing the sorted region by one.

Think of it like laying out playing cards face-up, scanning for the smallest, and placing it at the front.

Algorithm

For i from 0 to n-2:
- Find the index minIdx of the minimum element in arr[i..n-1]
- Swap arr[i] and arr[minIdx]

Visual Walkthrough

Input: [29, 10, 14, 37, 13]

i=0: Find min in [29, 10, 14, 37, 13] -> min=10 at index 1
     Swap arr[0] and arr[1]
     [10, 29, 14, 37, 13]
      ^sorted

i=1: Find min in [29, 14, 37, 13] -> min=13 at index 4
     Swap arr[1] and arr[4]
     [10, 13, 14, 37, 29]
      ^---^ sorted

i=2: Find min in [14, 37, 29] -> min=14 at index 2
     No swap needed (already in place)
     [10, 13, 14, 37, 29]
      ^-------^ sorted

i=3: Find min in [37, 29] -> min=29 at index 4
     Swap arr[3] and arr[4]
     [10, 13, 14, 29, 37]
      ^-----------^ sorted

Result: [10, 13, 14, 29, 37]

Why Selection Sort is NOT Stable

Stability means equal elements keep their original relative order. Selection sort breaks this because of long-range swaps.

Example: [4a, 3, 4b, 1]    (4a and 4b are both value 4)

i=0: min = 1 (index 3). Swap arr[0]=4a with arr[3]=1.
     [1, 3, 4b, 4a]
     Now 4a is AFTER 4b, but originally 4a was BEFORE 4b.
     Relative order of equal elements is broken -> NOT STABLE.

Complexity Analysis

Case	Time	Explanation
Best	O(n^2)	Always scans the entire unsorted region, even if already sorted
Average	O(n^2)	n(n-1)/2 comparisons always
Worst	O(n^2)	Same as average
Space	O(1)	In-place

Key property: Selection sort performs at most n-1 swaps. This is optimal for swap-minimization. Useful when writes are extremely expensive (e.g., flash memory).

C++ Code

CPP

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

When to Use

When the number of swaps must be minimized (each swap is very expensive)
Small arrays where simplicity matters more than performance
Otherwise, prefer insertion sort for O(n^2) algorithms

3. Insertion Sort

Intuition

Think of sorting a hand of playing cards. You pick up cards one at a time and insert each new card into the correct position among the cards you already hold. The cards in your hand are always sorted.

The array is conceptually divided into a sorted prefix and an unsorted suffix. For each element in the unsorted part, we "insert" it into its correct position in the sorted prefix by shifting larger elements one position to the right.

Algorithm

For i from 1 to n-1:
- key = arr[i]
- Shift all elements in arr[0..i-1] that are greater than key one position right
- Place key in the gap

Visual Walkthrough

Input: [7, 3, 5, 1, 9]

Step 1: key = 3, sorted part = [7]
   Compare 3 < 7: shift 7 right
   [_, 7, 5, 1, 9]   Insert 3 at position 0
   [3, 7, 5, 1, 9]
    ^--^ sorted

Step 2: key = 5, sorted part = [3, 7]
   Compare 5 < 7: shift 7 right
   Compare 5 > 3: stop
   [3, _, 7, 1, 9]   Insert 5 at position 1
   [3, 5, 7, 1, 9]
    ^-----^ sorted

Step 3: key = 1, sorted part = [3, 5, 7]
   Compare 1 < 7: shift 7 right
   Compare 1 < 5: shift 5 right
   Compare 1 < 3: shift 3 right
   [_, 3, 5, 7, 9]   Insert 1 at position 0
   [1, 3, 5, 7, 9]
    ^--------^ sorted

Step 4: key = 9, sorted part = [1, 3, 5, 7]
   Compare 9 > 7: stop, already in place
   [1, 3, 5, 7, 9]
    ^-----------^ sorted

Result: [1, 3, 5, 7, 9]

Why Insertion Sort is Excellent for Nearly-Sorted Data

If the array is nearly sorted, each element is close to its final position. The inner loop runs very few times per element. In the best case (already sorted), the inner loop never executes, giving O(n) time.

Number of shifts = number of inversions in the array. An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. For nearly-sorted arrays, inversions are few.

Complexity Analysis

Case	Time	Explanation
Best	O(n)	Already sorted; inner loop never runs
Average	O(n^2)	Roughly n^2/4 shifts
Worst	O(n^2)	Reverse sorted; every element shifts to position 0
Space	O(1)	In-place

C++ Code

CPP

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Binary Insertion Sort

We can use binary search to find the insertion point (reducing comparisons to O(log n) per element), but shifting still takes O(n) per element, so worst case remains O(n^2).

CPP

void binaryInsertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        // Binary search for insertion point in arr[0..i-1]
        int lo = 0, hi = i;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] <= key) lo = mid + 1;
            else hi = mid;
        }
        // Shift elements arr[lo..i-1] one position right
        for (int j = i; j > lo; j--) {
            arr[j] = arr[j - 1];
        }
        arr[lo] = key;
    }
}

When to Use

Small arrays (n < 16) --- used as the base case in quicksort/mergesort implementations
Nearly sorted data --- very fast due to few inversions
Online sorting --- elements arrive one at a time; each insertion is O(n) worst case
Adaptive sorting --- performance adapts to the existing order in the input

4. Merge Sort

CRITICAL FOR INTERVIEWS --- understand this inside out.

Intuition: The Divide and Conquer Paradigm

Merge sort follows a simple but powerful strategy:

Divide: Split the array into two halves
Conquer: Recursively sort each half
Combine: Merge the two sorted halves into one sorted array

The key insight is that merging two sorted arrays is easy and takes O(n) time. We just use two pointers, always picking the smaller element.

Visual: Split and Merge Phases

                     [38, 27, 43, 3, 9, 82, 10]
                               SPLIT
                    /                         \
          [38, 27, 43, 3]              [9, 82, 10]
              SPLIT                       SPLIT
           /          \                /          \
       [38, 27]    [43, 3]       [9, 82]        [10]
        SPLIT       SPLIT        SPLIT            |
       /     \     /     \      /     \           |
     [38]   [27] [43]   [3]  [9]   [82]        [10]
       \     /     \     /      \     /           |
        MERGE       MERGE        MERGE            |
       [27, 38]    [3, 43]      [9, 82]         [10]
           \          /                \          /
            MERGE                       MERGE
       [3, 27, 38, 43]            [9, 10, 82]
                    \                /
                     MERGE
              [3, 9, 10, 27, 38, 43, 82]

The Merge Operation in Detail

This is the heart of merge sort. Given two sorted arrays, produce one sorted array.

Merge [3, 27, 38, 43] and [9, 10, 82]:

Left:   [3, 27, 38, 43]     Right: [9, 10, 82]
         ^                          ^
         i                          j

Step 1: 3 < 9   -> take 3.   Result: [3]
         i=1                  j=0

Step 2: 27 > 9  -> take 9.   Result: [3, 9]
         i=1                  j=1

Step 3: 27 > 10 -> take 10.  Result: [3, 9, 10]
         i=1                  j=2

Step 4: 27 < 82 -> take 27.  Result: [3, 9, 10, 27]
         i=2                  j=2

Step 5: 38 < 82 -> take 38.  Result: [3, 9, 10, 27, 38]
         i=3                  j=2

Step 6: 43 < 82 -> take 43.  Result: [3, 9, 10, 27, 38, 43]
         i=4 (done)           j=2

Step 7: Copy remaining right. Result: [3, 9, 10, 27, 38, 43, 82]

Why Merge Sort is Stable

During the merge step, when left[i] == right[j], we always take left[i] first. This preserves the original relative order of equal elements, because left elements always came before right elements in the original array.

Complexity Analysis

Case	Time	Explanation
Best	O(n log n)	Always splits and merges; no shortcut
Average	O(n log n)	Same
Worst	O(n log n)	Same --- guaranteed!
Space	O(n)	Temporary array for merging

Recurrence: T(n) = 2T(n/2) + O(n) => T(n) = O(n log n) by Master Theorem.

Recursion tree (why O(n log n)):

Level 0:                    n                         work = n
Level 1:             n/2         n/2                  work = n
Level 2:          n/4   n/4   n/4   n/4              work = n
  ...              ...                                 ...
Level log n:     1  1  1  1 ... 1  1  1  1            work = n

Total levels: log n
Work per level: O(n)
Total: O(n log n)

Complete C++ Code

CPP

#include <bits/stdc++.h>
using namespace std;

void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> L(n1), R(n2);

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {       // <= ensures stability
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }

    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

// Wrapper
void mergeSort(vector<int>& arr) {
    if (arr.size() <= 1) return;
    mergeSort(arr, 0, arr.size() - 1);
}

Optimized Merge Sort (with temp buffer reuse)

CPP

void mergeOptimized(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
    for (int i = left; i <= right; i++) temp[i] = arr[i];

    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (temp[i] <= temp[j]) arr[k++] = temp[i++];
        else arr[k++] = temp[j++];
    }
    while (i <= mid) arr[k++] = temp[i++];
    // No need to copy remaining right elements --- they're already in arr
}

void mergeSortOptimized(vector<int>& arr, vector<int>& temp, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSortOptimized(arr, temp, left, mid);
    mergeSortOptimized(arr, temp, mid + 1, right);
    mergeOptimized(arr, temp, left, mid, right);
}

void mergeSort(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return;
    vector<int> temp(n);
    mergeSortOptimized(arr, temp, 0, n - 1);
}

Bottom-Up (Iterative) Merge Sort

CPP

void mergeSortBottomUp(vector<int>& arr) {
    int n = arr.size();
    vector<int> temp(n);

    for (int width = 1; width < n; width *= 2) {
        for (int left = 0; left < n; left += 2 * width) {
            int mid = min(left + width - 1, n - 1);
            int right = min(left + 2 * width - 1, n - 1);
            if (mid < right) {
                mergeOptimized(arr, temp, left, mid, right);
            }
        }
    }
}

When to Use Merge Sort

Need guaranteed O(n log n) worst-case performance
Need stability (equal elements keep relative order)
Sorting linked lists (no random access needed; merge is natural)
External sorting (sorting data that doesn't fit in memory)
Counting inversions (classic application)

Application: Counting Inversions

An inversion is a pair (i, j) where i < j but arr[i] > arr[j]. Merge sort can count all inversions in O(n log n) by counting cross-inversions during the merge step.

CPP

long long mergeCount(vector<int>& arr, vector<int>& temp, int left, int mid, int right) {
    long long inversions = 0;
    int i = left, j = mid + 1, k = left;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
            inversions += (mid - i + 1);  // All remaining in left are > arr[j]
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (int p = left; p <= right; p++) arr[p] = temp[p];
    return inversions;
}

long long countInversions(vector<int>& arr, vector<int>& temp, int left, int right) {
    if (left >= right) return 0;
    int mid = left + (right - left) / 2;
    long long count = 0;
    count += countInversions(arr, temp, left, mid);
    count += countInversions(arr, temp, mid + 1, right);
    count += mergeCount(arr, temp, left, mid, right);
    return count;
}

5. Quick Sort

CRITICAL FOR INTERVIEWS --- the most-asked sorting algorithm.

Intuition

Choose a pivot element
Partition: rearrange so that elements < pivot are on the left, elements > pivot on the right
Recursively sort left and right partitions

After partitioning, the pivot is in its final sorted position. This is the key insight.

The Partition Step: Two Schemes

Lomuto Partition Scheme

The simpler scheme. Uses the last element as pivot.

Partition [3, 6, 8, 10, 1, 2, 1] with pivot = 1 (last element)

i = index of boundary (elements <= pivot end at index i)
j = scanning pointer

Initial: i = -1, pivot = arr[6] = 1

j=0: arr[0]=3 > 1, skip
     [3, 6, 8, 10, 1, 2, 1]
      j                       i=-1

j=1: arr[1]=6 > 1, skip

j=2: arr[2]=8 > 1, skip

j=3: arr[3]=10 > 1, skip

j=4: arr[4]=1 <= 1, i++ (i=0), swap arr[0] and arr[4]
     [1, 6, 8, 10, 3, 2, 1]
      i              j

j=5: arr[5]=2 > 1, skip

Final: swap arr[i+1] and arr[hi] (pivot)
       swap arr[1] and arr[6]
     [1, 1, 8, 10, 3, 2, 6]
         ^
     pivot in final position at index 1

Left partition:  [1]       (indices 0..0)
Right partition: [8, 10, 3, 2, 6]  (indices 2..6)

CPP

int lomutoPartition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;

    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[hi]);
    return i + 1;
}

Hoare Partition Scheme

More efficient (fewer swaps on average). Uses two pointers that move toward each other.

Partition [3, 6, 8, 10, 1, 2, 1] with pivot = arr[0] = 3

i starts at left, j starts at right.
Move i right until arr[i] >= pivot.
Move j left until arr[j] <= pivot.
Swap and continue until i >= j.

Initial: pivot = 3, i = 0, j = 6

i moves right: arr[0]=3 >= 3, stop at i=0
j moves left:  arr[6]=1 <= 3, stop at j=6
Swap arr[0] and arr[6]:
     [1, 6, 8, 10, 1, 2, 3]
      i                    j

i moves right: arr[1]=6 >= 3, stop at i=1
j moves left:  arr[6]=3 >= 3, arr[5]=2 <= 3, stop at j=5
Swap arr[1] and arr[5]:
     [1, 2, 8, 10, 1, 6, 3]
         i              j

i moves right: arr[2]=8 >= 3, stop at i=2
j moves left:  arr[4]=1 <= 3, stop at j=4
Swap arr[2] and arr[4]:
     [1, 2, 1, 10, 8, 6, 3]
            i       j

i moves right: arr[3]=10 >= 3, stop at i=3
j moves left:  arr[2]=1 <= 3, stop at j=2
Now i > j, stop.

Return j = 2.
Left partition:  [1, 2, 1]       (indices 0..2)
Right partition: [10, 8, 6, 3]   (indices 3..6)

CPP

int hoarePartition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[lo + (hi - lo) / 2];  // middle element as pivot
    int i = lo - 1, j = hi + 1;

    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(arr[i], arr[j]);
    }
}

Hoare vs Lomuto:

Hoare does ~3x fewer swaps on average
Hoare is slightly harder to implement correctly
Hoare returns a partition point, not the pivot's final index (subtle difference)

Why O(n^2) Worst Case and How to Avoid It

Worst case occurs when the pivot is always the smallest or largest element, creating highly unbalanced partitions:

Already sorted: [1, 2, 3, 4, 5] with last element as pivot

Partition 1: pivot=5, left=[1,2,3,4], right=[]  -> n-1 work
Partition 2: pivot=4, left=[1,2,3], right=[]     -> n-2 work
Partition 3: pivot=3, left=[1,2], right=[]        -> n-3 work
...
Total: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)

Solutions:

Random pivot selection: Choose a random element as pivot. Makes worst case astronomically unlikely.

CPP

int randomPartition(vector<int>& arr, int lo, int hi) {
    int randomIdx = lo + rand() % (hi - lo + 1);
    swap(arr[randomIdx], arr[hi]);
    return lomutoPartition(arr, lo, hi);
}

Median-of-three: Choose the median of first, middle, and last elements.

CPP

int medianOfThree(vector<int>& arr, int lo, int hi) {
    int mid = lo + (hi - lo) / 2;
    if (arr[lo] > arr[mid]) swap(arr[lo], arr[mid]);
    if (arr[lo] > arr[hi])  swap(arr[lo], arr[hi]);
    if (arr[mid] > arr[hi]) swap(arr[mid], arr[hi]);
    // Now arr[lo] <= arr[mid] <= arr[hi]
    swap(arr[mid], arr[hi - 1]);  // Place median as pivot
    return arr[hi - 1];
}

Three-Way Partition (Dutch National Flag)

When there are many duplicate elements, standard quicksort degrades. Three-way partition handles this by dividing into three regions: < pivot, == pivot, > pivot.

Input: [4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4]
Pivot = 4

After 3-way partition:
[1, 1] [4, 4, 4, 4, 4, 4, 4, 4] [9, 9, 9]
 < 4            == 4               > 4

Only recurse on the < and > parts. The == part is done!

CPP

// Dutch National Flag: partition into <, ==, > pivot
pair<int,int> threeWayPartition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[lo + rand() % (hi - lo + 1)];
    int lt = lo, gt = hi, i = lo;

    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr[lt], arr[i]);
            lt++;
            i++;
        } else if (arr[i] > pivot) {
            swap(arr[i], arr[gt]);
            gt--;
        } else {
            i++;
        }
    }
    // arr[lo..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..hi] > pivot
    return {lt, gt};
}

void quickSort3Way(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    auto [lt, gt] = threeWayPartition(arr, lo, hi);
    quickSort3Way(arr, lo, lt - 1);
    quickSort3Way(arr, gt + 1, hi);
}

Complete Quick Sort with Lomuto + Random Pivot

CPP

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int>& arr, int lo, int hi) {
    // Random pivot
    int randomIdx = lo + rand() % (hi - lo + 1);
    swap(arr[randomIdx], arr[hi]);

    int pivot = arr[hi];
    int i = lo - 1;

    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            swap(arr[++i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[hi]);
    return i + 1;
}

void quickSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
}

void quickSort(vector<int>& arr) {
    srand(time(0));
    quickSort(arr, 0, (int)arr.size() - 1);
}

Complete Quick Sort with Hoare Partition

CPP

void quickSortHoare(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = arr[lo + (hi - lo) / 2];
    int i = lo - 1, j = hi + 1;
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) break;
        swap(arr[i], arr[j]);
    }
    quickSortHoare(arr, lo, j);      // Note: j, not j-1 (Hoare scheme)
    quickSortHoare(arr, j + 1, hi);
}

Tail Recursion Optimization

To limit stack depth to O(log n) even in worst case:

CPP

void quickSortTailOpt(vector<int>& arr, int lo, int hi) {
    while (lo < hi) {
        int p = partition(arr, lo, hi);
        // Recurse on smaller partition, iterate on larger
        if (p - lo < hi - p) {
            quickSortTailOpt(arr, lo, p - 1);
            lo = p + 1;
        } else {
            quickSortTailOpt(arr, p + 1, hi);
            hi = p - 1;
        }
    }
}

Complexity Analysis

Case	Time	Explanation
Best	O(n log n)	Perfectly balanced partitions each time
Average	O(n log n)	Random pivot gives balanced partitions with high probability
Worst	O(n^2)	Always picking min/max as pivot (mitigated by randomization)
Space	O(log n)	Recursion stack (O(n) worst case without tail optimization)

When to Use

General-purpose sorting --- fastest in practice due to low constant factor
In-place sorting needed --- only O(log n) extra space
Cache-friendly --- sequential memory access patterns
Not needed: when stability is required, when guaranteed O(n log n) is critical

6. Heap Sort

Intuition

Build a max-heap from the array
Repeatedly extract the maximum (root of heap) and place it at the end
After each extraction, the heap shrinks by one and the sorted region grows

A max-heap is a complete binary tree where every parent is >= its children.

Array Representation of a Heap

For 0-indexed array:
  Parent of i:      (i - 1) / 2
  Left child of i:  2*i + 1
  Right child of i: 2*i + 2

Array: [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

Tree representation:
              16
           /      \
         14        10
        /  \      /  \
       8    7    9    3
      / \  /
     2  4 1

Heapify Operation

heapify(i): Fix the heap property at node i by "sinking" it down.

heapify(1) on [16, 4, 10, 14, 7, 9, 3, 2, 8, 1]:

       4
      / \
    14    ?

4 < 14, so swap with larger child:

       14
      / \
     4    ?

Now check children of new position of 4:
4 < 8, swap:

       14
      / \
     8    ?
    / \
   2   4

Heap property restored at this subtree.

Visual Walkthrough of Heap Sort

Input: [4, 10, 3, 5, 1]

Step 1: Build max-heap (heapify from last non-leaf to root)

  Array: [4, 10, 3, 5, 1]

  Tree:     4
           / \
         10    3
        /  \
       5    1

  Heapify index 1 (value 10): children are 5,1. 10 > both. OK.
  Heapify index 0 (value 4): largest child is 10. Swap.

       10                10
      / \    ->         / \
     4    3            5    3
    / \               / \
   5   1             4   1

  Max-heap: [10, 5, 3, 4, 1]

Step 2: Extract max repeatedly

  Swap arr[0]=10 with arr[4]=1, reduce heap size
  [1, 5, 3, 4, | 10]
  Heapify root: 1 sinks -> [5, 4, 3, 1, | 10]

  Swap arr[0]=5 with arr[3]=1, reduce heap size
  [1, 4, 3, | 5, 10]
  Heapify root: 1 sinks -> [4, 1, 3, | 5, 10]

  Swap arr[0]=4 with arr[2]=3, reduce heap size
  [3, 1, | 4, 5, 10]
  Heapify root: OK (3 > 1)

  Swap arr[0]=3 with arr[1]=1
  [1, | 3, 4, 5, 10]

Result: [1, 3, 4, 5, 10]

Complexity Analysis

Case	Time	Explanation
Best	O(n log n)	Even if sorted, still does all heapify operations
Average	O(n log n)	Each of n extractions takes O(log n)
Worst	O(n log n)	Same --- guaranteed
Space	O(1)	In-place! (No extra array needed)

Build-heap is O(n), not O(n log n)! The math: sum of (n/2^h) * h for h=0 to log n converges to O(n). But the extraction phase is O(n log n), dominating total.

C++ Code

CPP

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();

    // Build max-heap (start from last non-leaf node)
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract elements one by one
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);      // Move current max to end
        heapify(arr, i, 0);       // Heapify reduced heap
    }
}

When to Use

Need guaranteed O(n log n) with O(1) extra space
Used in C++ STL partial_sort() (uses a heap of size k)
Real-time systems where worst-case guarantees matter
Rarely used as a standalone sort in practice (poor cache performance compared to quicksort)

7. Counting Sort

Intuition

Instead of comparing elements, count how many times each value appears, then reconstruct the sorted array from the counts. This only works when the range of values is known and reasonably small.

Algorithm

Find the maximum value k in the array
Create a count array of size k+1, initialized to 0
Count occurrences: count[arr[i]]++
Compute prefix sums: count[i] += count[i-1] (gives final positions)
Build output array using prefix sums (scan right-to-left for stability)
Copy output back

Visual Step-by-Step

Input: [4, 2, 2, 8, 3, 3, 1]
Max value k = 8

Step 1: Count occurrences
  Index:  0  1  2  3  4  5  6  7  8
  Count: [0, 1, 2, 2, 1, 0, 0, 0, 1]
          0  1  2  3  4  5  6  7  8

Step 2: Prefix sums (cumulative count)
  Count: [0, 1, 3, 5, 6, 6, 6, 6, 7]

  Meaning: count[i] = number of elements <= i
  count[3] = 5 means there are 5 elements <= 3

Step 3: Build output (right to left for stability)
  Process arr[6]=1: count[1]=1, output[0]=1, count[1]-- -> 0
  Process arr[5]=3: count[3]=5, output[4]=3, count[3]-- -> 4
  Process arr[4]=3: count[3]=4, output[3]=3, count[3]-- -> 3
  Process arr[3]=8: count[8]=7, output[6]=8, count[8]-- -> 6
  Process arr[2]=2: count[2]=3, output[2]=2, count[2]-- -> 2
  Process arr[1]=2: count[2]=2, output[1]=2, count[2]-- -> 1
  Process arr[0]=4: count[4]=6, output[5]=4, count[4]-- -> 5

  Output: [1, 2, 2, 3, 3, 4, 8]

Complexity

Aspect	Value	Explanation
Time	O(n + k)	Count in O(n), prefix sum in O(k), place in O(n)
Space	O(n + k)	Output array O(n) + count array O(k)
Stable	Yes	Right-to-left placement preserves order

When k = O(n), this is linear time --- beating the O(n log n) lower bound for comparison-based sorting!

C++ Code

CPP

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;

    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;

    vector<int> count(range, 0);
    vector<int> output(arr.size());

    // Count occurrences
    for (int x : arr) count[x - minVal]++;

    // Prefix sum
    for (int i = 1; i < range; i++) count[i] += count[i - 1];

    // Build output (right to left for stability)
    for (int i = arr.size() - 1; i >= 0; i--) {
        output[count[arr[i] - minVal] - 1] = arr[i];
        count[arr[i] - minVal]--;
    }

    arr = output;
}

Limitations

Only works for integer (or integer-like) keys
Impractical when range k is much larger than n (e.g., sorting 100 elements with values up to 10^9)
Needs non-negative values (or offset by minimum)

When to Use

Small range of integer values (k = O(n))
As a subroutine in radix sort
Sorting characters (k = 26 or 256)

8. Radix Sort

Intuition

Sort numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). Use a stable sort (like counting sort) for each digit. Because the subroutine is stable, sorting by digit d preserves the order from digit d-1.

Algorithm (LSD Radix Sort)

Find the maximum number to determine the number of digits d
For each digit position (ones, tens, hundreds, ...):
- Use counting sort on that digit

Visual Walkthrough

Input: [170, 45, 75, 90, 802, 24, 2, 66]

Digit 1 (ones place):        Digit 2 (tens place):        Digit 3 (hundreds place):
Sort by last digit            Sort by middle digit          Sort by first digit

17[0]  -> 0                   [0]2  -> 0                   [0]02  -> 0
 4[5]  -> 5                   [0]2  -> 0                   [0]24  -> 0
 7[5]  -> 5                   [2]4  -> 2                   [0]45  -> 0
 9[0]  -> 0                   [4]5  -> 4                   [0]66  -> 0
80[2]  -> 2                   [6]6  -> 6                   [0]75  -> 0
 2[4]  -> 4                   [7]0  -> 7                   [0]90  -> 0
  [2]  -> 2                   [7]5  -> 7                   [1]70  -> 1
 6[6]  -> 6                   [9]0  -> 9                   [8]02  -> 8

After sort by ones:           After sort by tens:           After sort by hundreds:
[170, 90, 802, 2, 24, 45,    [802, 2, 24, 45, 66, 170,    [2, 24, 45, 66, 75, 90,
 75, 66]                       75, 90]                      170, 802]

Result: [2, 24, 45, 66, 75, 90, 170, 802]

Complexity

Aspect	Value	Explanation
Time	O(d(n+k))	d passes of counting sort on n elements with k=10 (digits)
Space	O(n + k)	Counting sort workspace
Stable	Yes	Uses stable counting sort

For w-bit integers, if we use base b = n, we get d = w/log(n) passes with k = n, giving O(w*n/log(n)). For 32-bit integers: O(n * 32/log(n)).

C++ Code

CPP

void countingSortByDigit(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n);
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    arr = output;
}

void radixSort(vector<int>& arr) {
    if (arr.empty()) return;
    int maxVal = *max_element(arr.begin(), arr.end());

    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

Note: This implementation only handles non-negative integers. For negative numbers, separate into negative/positive arrays, sort each, then merge.

Radix Sort with Base 256 (Byte-level)

For 32-bit integers, only 4 passes needed:

CPP

void radixSort256(vector<int>& arr) {
    int n = arr.size();
    vector<int> temp(n);

    for (int shift = 0; shift < 32; shift += 8) {
        int count[256] = {0};

        for (int i = 0; i < n; i++)
            count[(arr[i] >> shift) & 0xFF]++;

        for (int i = 1; i < 256; i++)
            count[i] += count[i - 1];

        for (int i = n - 1; i >= 0; i--)
            temp[--count[(arr[i] >> shift) & 0xFF]] = arr[i];

        swap(arr, temp);
    }
}

Note: This implementation only handles non-negative integers. For negative numbers, separate into negative/positive arrays, sort each, then merge.

When to Use

Sorting integers with bounded range
Sorting fixed-length strings
When n is large and the number of digits d is small

9. Bucket Sort

Intuition

Distribute elements into several "buckets", sort each bucket individually (using insertion sort or any other sort), then concatenate all buckets.

Works best when input is uniformly distributed over a known range.

Algorithm

Create k empty buckets
Distribute elements into buckets based on value
Sort each bucket (insertion sort for small buckets)
Concatenate all buckets

Visual with Uniform Distribution

Input: [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68]
Using 10 buckets (for range [0, 1)):

Bucket 0 [0.0, 0.1):
Bucket 1 [0.1, 0.2): 0.17, 0.12
Bucket 2 [0.2, 0.3): 0.26, 0.21, 0.23
Bucket 3 [0.3, 0.4): 0.39
Bucket 4 [0.4, 0.5):
Bucket 5 [0.5, 0.6):
Bucket 6 [0.6, 0.7): 0.68
Bucket 7 [0.7, 0.8): 0.78, 0.72
Bucket 8 [0.8, 0.9):
Bucket 9 [0.9, 1.0): 0.94

Sort each bucket:
Bucket 1: [0.12, 0.17]
Bucket 2: [0.21, 0.23, 0.26]
Bucket 7: [0.72, 0.78]

Concatenate:
[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]

Complexity

Case	Time	Explanation
Best	O(n + k)	Uniform distribution, each bucket has ~1 element
Average	O(n + k)	With uniform distribution and k = O(n)
Worst	O(n^2)	All elements in one bucket (degenerates to insertion sort)
Space	O(n + k)	Buckets

C++ Code

CPP

void bucketSort(vector<float>& arr) {
    int n = arr.size();
    if (n <= 1) return;

    vector<vector<float>> buckets(n);

    // Distribute into buckets
    for (float val : arr) {
        int idx = (int)(val * n);  // assumes values in [0, 1)
        if (idx >= n) idx = n - 1;
        buckets[idx].push_back(val);
    }

    // Sort each bucket
    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());  // or insertion sort
    }

    // Concatenate
    int index = 0;
    for (auto& bucket : buckets) {
        for (float val : bucket) {
            arr[index++] = val;
        }
    }
}

For Integer Bucket Sort

CPP

void bucketSortInt(vector<int>& arr) {
    if (arr.empty()) return;
    int minVal = *min_element(arr.begin(), arr.end());
    int maxVal = *max_element(arr.begin(), arr.end());
    int range = maxVal - minVal + 1;
    int bucketCount = max(1, (int)arr.size());

    vector<vector<int>> buckets(bucketCount);

    for (int val : arr) {
        int idx = (long long)(val - minVal) * (bucketCount - 1) / range;
        buckets[idx].push_back(val);
    }

    for (auto& bucket : buckets) {
        sort(bucket.begin(), bucket.end());
    }

    int index = 0;
    for (auto& bucket : buckets) {
        for (int val : bucket) {
            arr[index++] = val;
        }
    }
}

When to Use

Uniformly distributed data over a known range
Floating point numbers in [0, 1)
When you can choose a good hash function to distribute evenly

Quick Sort vs Merge Sort --- The Deep Comparison

This is a common interview question. Know the tradeoffs deeply.

Worst Case O(n²) O(n log n)

Average Case O(n log n) O(n log n)

Space O(log n) stack O(n) auxiliary

Stable No Yes

In-Place Yes (mostly) No

Cache Performance Excellent Good

Constant Factor Small (2-3x faster) Larger

Adaptive No (needs randomize) No

Parallelizable Moderate Excellent

External Sort No Yes

Linked List Sort Bad (no random acc.) Excellent

Why Quick Sort is Faster in Practice (despite same O(n log n)):

Cache locality: Quicksort works on contiguous memory. Mergesort copies to temp arrays.
Fewer data movements: Quicksort swaps in-place. Mergesort copies every element.
Branch prediction: Quicksort's partition has predictable branches.
No allocation: Quicksort needs no extra memory allocation (mergesort allocates O(n)).

When to Choose Merge Sort Over Quick Sort:

Stability is required
Guaranteed O(n log n) worst case is needed
Sorting linked lists
External sorting (data on disk)
Need to parallelize easily

C++ STL sort()

std::sort() uses Introsort (Introspective Sort), a hybrid algorithm:

STL Functions:

Function	Algorithm	Stable	Use Case
`sort()`	Introsort	No	General purpose
`stable_sort()`	Merge sort (+ insertion)	Yes	When stability needed
`partial_sort()`	Heap-based	No	Get top k elements
`nth_element()`	Quickselect (Introselect)	No	Find kth element in O(n) avg

CPP

#include <algorithm>
#include <vector>
using namespace std;

vector<int> arr = {5, 3, 8, 1, 2};

// Sort ascending
sort(arr.begin(), arr.end());

// Sort descending
sort(arr.begin(), arr.end(), greater<int>());

// Sort with custom comparator
sort(arr.begin(), arr.end(), [](int a, int b) {
    return a > b;  // descending
});

// Stable sort
stable_sort(arr.begin(), arr.end());

// Partial sort: place k smallest elements at the front, sorted
partial_sort(arr.begin(), arr.begin() + 3, arr.end());

// nth_element: partition around nth element
nth_element(arr.begin(), arr.begin() + 2, arr.end());
// arr[2] is now what it would be in sorted order
// elements before it are <= arr[2], elements after are >= arr[2]

SEARCHING ALGORITHMS

1. Linear Search --- O(n)

Intuition

Check every element one by one until the target is found or the array is exhausted. No prerequisites on the data structure.

C++ Code

CPP

int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < (int)arr.size(); i++) {
        if (arr[i] == target) return i;
    }
    return -1;  // not found
}

Sentinel Linear Search

Slightly optimized: place target at end to eliminate bounds check in loop.

CPP

int sentinelSearch(vector<int>& arr, int target) {
    int n = arr.size();
    if (n == 0) return -1;

    int last = arr[n - 1];
    arr[n - 1] = target;  // sentinel

    int i = 0;
    while (arr[i] != target) i++;

    arr[n - 1] = last;  // restore

    if (i < n - 1 || last == target) return i;
    return -1;
}

When to Use

Unsorted data (no other option)
Small arrays (overhead of binary search not worth it)
Single search on unsorted data (not worth sorting first)
Linked lists (no random access for binary search)

2. Binary Search --- O(log n) (CRITICAL for interviews)

Prerequisite

The array must be sorted (or have a monotonic property).

The Core Idea

At each step, eliminate half of the remaining search space. Compare the target with the middle element:

If equal: found it
If target < middle: search left half
If target > middle: search right half

Visual Walkthrough

Search for 7 in [1, 3, 5, 7, 9, 11, 13]

Step 1: lo=0, hi=6, mid=3
  [1, 3, 5, 7, 9, 11, 13]
   lo       ^mid        hi
  arr[3]=7 == 7 -> FOUND at index 3!

Search for 9 in [1, 3, 5, 7, 9, 11, 13]

Step 1: lo=0, hi=6, mid=3
  [1, 3, 5, 7, 9, 11, 13]
   lo       ^mid        hi
  arr[3]=7 < 9 -> search right: lo=4

Step 2: lo=4, hi=6, mid=5
  [1, 3, 5, 7, 9, 11, 13]
                  lo ^mid hi
  arr[5]=11 > 9 -> search left: hi=4

Step 3: lo=4, hi=4, mid=4
  [1, 3, 5, 7, 9, 11, 13]
                  ^
                lo=hi=mid
  arr[4]=9 == 9 -> FOUND at index 4!

Search for 6 in [1, 3, 5, 7, 9, 11, 13]

Step 1: lo=0, hi=6, mid=3 -> 7 > 6, hi=2
Step 2: lo=0, hi=2, mid=1 -> 3 < 6, lo=2
Step 3: lo=2, hi=2, mid=2 -> 5 < 6, lo=3
Step 4: lo=3 > hi=2 -> NOT FOUND

Why `lo + (hi - lo) / 2` instead of `(lo + hi) / 2`?

If lo = 2,000,000,000 and hi = 2,000,000,000
Then lo + hi = 4,000,000,000 which OVERFLOWS int (max ~2.1 billion)

lo + (hi - lo) / 2 = 2,000,000,000 + 0 = 2,000,000,000 (safe!)

The Three Essential Templates

Template 1: Find Exact Value

CPP

int binarySearch(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;  // not found
}

Key points:

lo <= hi: we keep searching when range has at least 1 element
Both lo and hi move past mid (never include mid again)
Returns -1 if not found

Template 2: Lower Bound (first element >= target)

CPP

int lowerBound(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid;  // arr[mid] >= target: might be the answer
    }
    return lo;  // lo == hi == insertion point
}

Key points:

hi = arr.size() (one past last element) --- the answer could be "past the end"
lo < hi: terminates when lo == hi
When arr[mid] >= target, set hi = mid (mid could be the answer, don't skip it)
Always returns a valid index (or n if all elements < target)

Example: lowerBound([1, 3, 5, 5, 7], 5)

lo=0, hi=5, mid=2: arr[2]=5 >= 5, hi=2
lo=0, hi=2, mid=1: arr[1]=3 < 5, lo=2
lo=2 == hi=2: return 2

arr[2] = 5, which is the FIRST element >= 5. Correct!

Template 3: Upper Bound (first element > target)

CPP

int upperBound(vector<int>& arr, int target) {
    int lo = 0, hi = (int)arr.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

The only difference from lower bound: <= instead of < in the condition.

Example: upperBound([1, 3, 5, 5, 7], 5)

lo=0, hi=5, mid=2: arr[2]=5 <= 5, lo=3
lo=3, hi=5, mid=4: arr[4]=7 > 5, hi=4
lo=3, hi=4, mid=3: arr[3]=5 <= 5, lo=4
lo=4 == hi=4: return 4

arr[4] = 7, which is the FIRST element > 5. Correct!

Using lower_bound and upper_bound together:

Count of value 5 in [1, 3, 5, 5, 7]:
  lower_bound = 2 (first 5)
  upper_bound = 4 (first element after last 5)
  count = upper_bound - lower_bound = 4 - 2 = 2

Complexity

Array of n elements:
Step 1: n elements
Step 2: n/2 elements
Step 3: n/4 elements
...
Step k: n/2^k elements

When n/2^k = 1 -> k = log2(n)

Time: O(log n)
Space: O(1) iterative, O(log n) recursive

For n = 1,000,000: at most ~20 steps. For n = 1,000,000,000: at most ~30 steps.

Binary Search on Answer (Parametric Search)

This is perhaps the most powerful and frequently tested variant. The idea:

Instead of searching for an element in an array, search for the optimal value of some parameter where a condition flips from false to true (or vice versa).

The search space is not an array but a range of possible answers.

Template: Find minimum x such that condition(x) is true

Condition over the answer space:
  x:     1  2  3  4  5  6  7  8  9  10
  f(x):  F  F  F  F  T  T  T  T  T  T
                      ^
         We want this transition point (first True)

CPP

// Find minimum x in [lo, hi] such that condition(x) is true
// Precondition: there exists some threshold where condition flips from F to T
int binarySearchOnAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (condition(mid)) {
            hi = mid;       // mid might be the answer
        } else {
            lo = mid + 1;   // mid is too small
        }
    }
    return lo;  // lo == hi == first value where condition is true
}

Template: Find maximum x such that condition(x) is true

  x:     1  2  3  4  5  6  7  8  9  10
  f(x):  T  T  T  T  T  T  F  F  F  F
                         ^
         We want this (last True)

CPP

int binarySearchMaxTrue(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;  // Round UP to avoid infinite loop
        if (condition(mid)) {
            lo = mid;       // mid satisfies, maybe we can go higher
        } else {
            hi = mid - 1;   // mid fails, go lower
        }
    }
    return lo;
}

IMPORTANT: Note (hi - lo + 1) / 2 (round up) in the "find max" template. Without this, when lo + 1 == hi and condition(lo) is true, mid = lo, lo = mid = lo, and we infinite loop.

Example: Koko Eating Bananas (LC 875)

Koko has piles of bananas. She can eat k bananas/hour from one pile. She has h hours total. Find the minimum k such that she can eat all bananas.

Piles: [3, 6, 7, 11], h = 8

Answer space: k from 1 to max(piles) = 11
For each k, calculate hours needed: sum(ceil(pile/k) for each pile)

k=1:  3+6+7+11 = 27 hours (> 8, too slow)
k=2:  2+3+4+6  = 15 hours (> 8, too slow)
k=3:  1+2+3+4  = 10 hours (> 8, too slow)
k=4:  1+2+2+3  = 8  hours (<= 8, works!)
k=5:  1+2+2+3  = 8  hours (works)
...

The condition flips at k=4. Answer: 4.

CPP

int minEatingSpeed(vector<int>& piles, int h) {
    int lo = 1, hi = *max_element(piles.begin(), piles.end());

    auto canFinish = [&](int k) -> bool {
        long long hours = 0;
        for (int pile : piles) {
            hours += (pile + k - 1) / k;  // ceil(pile / k)
        }
        return hours <= h;
    };

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Example: Split Array Largest Sum (LC 410)

Split array into m subarrays to minimize the maximum subarray sum.

nums = [7, 2, 5, 10, 8], m = 2

Binary search on the answer (maximum subarray sum):
  lo = max(nums) = 10  (at minimum, one subarray must hold the largest element)
  hi = sum(nums) = 32  (at maximum, one subarray holds everything)

  For a given max_sum, check if we can split into <= m subarrays:
    Greedily fill subarrays until adding next element would exceed max_sum.

  mid=21: [7,2,5] sum=14, [10,8] sum=18. 2 subarrays <= 2. Works -> hi=21
  mid=15: [7,2,5] sum=14, [10] sum=10, [8] sum=8. 3 subarrays > 2. Fail -> lo=16
  mid=18: [7,2,5] sum=14, [10,8] sum=18. 2 subarrays <= 2. Works -> hi=18
  mid=17: [7,2,5] sum=14, [10] sum=10... wait, 10+8=18 > 17. [10],[8]. 3 > 2. Fail -> lo=18
  lo=18==hi=18. Answer: 18.

CPP

int splitArray(vector<int>& nums, int m) {
    int lo = *max_element(nums.begin(), nums.end());
    int hi = accumulate(nums.begin(), nums.end(), 0);

    auto canSplit = [&](int maxSum) -> bool {
        int count = 1, currentSum = 0;
        for (int num : nums) {
            if (currentSum + num > maxSum) {
                count++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }
        return count <= m;
    };

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canSplit(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Binary Search on Floating Point

When searching over real numbers, we cannot use lo < hi (they may never be exactly equal). Use a fixed number of iterations or an epsilon.

CPP

// Find sqrt(x) using binary search
double mySqrt(double x) {
    double lo = 0, hi = max(1.0, x);
    for (int iter = 0; iter < 100; iter++) {  // 100 iterations gives ~10^-30 precision
        double mid = lo + (hi - lo) / 2;
        if (mid * mid < x) lo = mid;
        else hi = mid;
    }
    return lo;
}

3. Ternary Search

Intuition

Binary search works on monotonic functions. Ternary search works on unimodal functions (functions with a single peak or valley).

Divide the range into three parts using two points, m1 and m2. Compare f(m1) and f(m2) to determine which third to eliminate.

Finding the peak of a unimodal function:

        *  *
       *    *
      *      *
     *        *
    *          *
   m1    m2

If f(m1) < f(m2): peak is to the right of m1 -> lo = m1
If f(m1) > f(m2): peak is to the left of m2, so hi = m2

Complexity

Each step eliminates 1/3 of the range. After k steps, range = (2/3)^k * original.

T(n) = O(log_{3/2}(n)) which is O(log n), but with a larger constant than binary search.

In practice, binary search on the derivative (when possible) is preferred over ternary search because binary search has a smaller constant factor.

C++ Code

CPP

// Find x in [lo, hi] that maximizes f(x) (unimodal function)
double ternarySearchMax(double lo, double hi, function<double(double)> f) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1;
        else hi = m2;
    }
    return lo + (hi - lo) / 2;
}

// Integer version: find peak
int ternarySearchPeak(int lo, int hi, function<int(int)> f) {
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1 + 1;
        else hi = m2 - 1;
    }
    // Check remaining 1-3 elements
    int best = lo;
    for (int i = lo; i <= hi; i++) {
        if (f(i) > f(best)) best = i;
    }
    return best;
}

Comparison with Binary Search

Aspect	Binary Search	Ternary Search
Requirement	Monotonic function	Unimodal function
Comparisons per step	1	2
Reduction per step	1/2	1/3
Steps for range n	log2(n)	log_{3/2}(n) ~ 1.71 * log2(n)
Total comparisons	log2(n)	2 * log_{3/2}(n) ~ 3.42 * log2(n)

Binary search is strictly better when applicable. Use ternary search only when you cannot reduce to binary search.

4. Exponential Search

Intuition

Useful for unbounded/infinite sorted arrays or when the target is near the beginning.

Find a range where the target might be: start with size 1, double until arr[bound] >= target
Binary search within the found range

Array:  [2, 3, 4, 10, 40, 50, 60, 70, 80, 90, 100, ...]
Target: 10

Step 1: Check arr[1]=3 < 10 -> bound=2
Step 2: Check arr[2]=4 < 10 -> bound=4
Step 3: Check arr[4]=40 >= 10 -> STOP

Binary search in arr[2..4] = [4, 10, 40]
Found 10 at index 3!

Complexity

Finding the range: O(log i) where i is the target's index
Binary search in range [bound/2, bound]: O(log i)
Total: O(log i) --- better than O(log n) when target is near the front

C++ Code

CPP

int exponentialSearch(vector<int>& arr, int target) {
    int n = arr.size();
    if (n == 0) return -1;
    if (arr[0] == target) return 0;

    // Find range
    int bound = 1;
    while (bound < n && arr[bound] < target) {
        bound *= 2;
    }

    // Binary search in [bound/2, min(bound, n-1)]
    int lo = bound / 2;
    int hi = min(bound, n - 1);

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

When to Use

Infinite or very large sorted arrays
Target likely near the beginning
As a building block for other algorithms

STL Functions

CPP

#include <algorithm>
#include <vector>
using namespace std;

vector<int> arr = {1, 3, 5, 5, 7, 9, 11};

// lower_bound: iterator to first element >= value
auto it1 = lower_bound(arr.begin(), arr.end(), 5);
// *it1 = 5, it1 - arr.begin() = 2

// upper_bound: iterator to first element > value
auto it2 = upper_bound(arr.begin(), arr.end(), 5);
// *it2 = 7, it2 - arr.begin() = 4

// binary_search: returns true/false (not the position!)
bool found = binary_search(arr.begin(), arr.end(), 5);  // true

// equal_range: returns pair of {lower_bound, upper_bound}
auto [lo, hi] = equal_range(arr.begin(), arr.end(), 5);
// lo points to first 5, hi points to first 7
// count of 5s = hi - lo = 2

// nth_element: rearranges so that arr[k] is the element that would be
// at position k if sorted. Elements before k are <= arr[k], after are >= arr[k].
// O(n) average time (uses Quickselect / Introselect)
vector<int> v = {9, 4, 7, 2, 5, 1, 8, 3, 6};
nth_element(v.begin(), v.begin() + 4, v.end());
// v[4] is now the median (5th smallest)
// v[4] == 5 (what would be at index 4 in sorted order)

nth_element implements the Quickselect algorithm:

Average O(n), worst O(n^2)
C++ STL typically uses Introselect (quickselect + fallback) for O(n) worst case
Perfect for finding kth smallest/largest without full sort

Binary Search Patterns for Interviews

Pattern 1: Classic Sorted Array Search

CPP

// Standard binary search - already covered above
int search(vector<int>& nums, int target);

Pattern 2: Search in Rotated Sorted Array (LC 33)

Array: [4, 5, 6, 7, 0, 1, 2]    (rotated at index 4)
Target: 0

Key insight: At least one half is always sorted.
Use the sorted half to determine which side the target is on.

CPP

int search(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) return mid;

        if (nums[lo] <= nums[mid]) {
            // Left half [lo..mid] is sorted
            if (nums[lo] <= target && target < nums[mid]) {
                hi = mid - 1;  // target is in sorted left half
            } else {
                lo = mid + 1;  // target is in right half
            }
        } else {
            // Right half [mid..hi] is sorted
            if (nums[mid] < target && target <= nums[hi]) {
                lo = mid + 1;  // target is in sorted right half
            } else {
                hi = mid - 1;  // target is in left half
            }
        }
    }
    return -1;
}

Pattern 3: Search in 2D Matrix (LC 74)

Matrix (sorted row-wise, each row starts after prev row ends):
[[ 1,  3,  5,  7],
 [10, 11, 16, 20],
 [23, 30, 34, 60]]

Treat as a 1D sorted array of size m*n.
Index k -> row = k/n, col = k%n

CPP

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int lo = 0, hi = m * n - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int val = matrix[mid / n][mid % n];
        if (val == target) return true;
        if (val < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

Pattern 4: Find Peak Element (LC 162)

A peak element is strictly greater than its neighbors.
arr = [1, 2, 3, 1]  -> peak at index 2 (value 3)

Key insight: If arr[mid] < arr[mid+1], there's a peak to the right.
            If arr[mid] < arr[mid-1], there's a peak to the left.
            (Array boundaries are -infinity)

CPP

int findPeakElement(vector<int>& nums) {
    int lo = 0, hi = (int)nums.size() - 1;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < nums[mid + 1]) {
            lo = mid + 1;  // Peak is to the right
        } else {
            hi = mid;      // Peak is at mid or to the left
        }
    }
    return lo;
}

Pattern 5: Find Minimum in Rotated Sorted Array (LC 153)

CPP

int findMin(vector<int>& nums) {
    int lo = 0, hi = (int)nums.size() - 1;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) {
            lo = mid + 1;  // Minimum is in right half
        } else {
            hi = mid;      // Minimum is at mid or left
        }
    }
    return nums[lo];
}

Pattern 6: Koko Eating Bananas (LC 875)

Already covered in the "Binary Search on Answer" section above.

Pattern 7: Minimum Days to Make Bouquets (LC 1482)

bloomDay = [1, 10, 3, 10, 2], m = 3, k = 1
Need m bouquets of k adjacent flowers. Return minimum days.

Binary search on answer: day from min(bloomDay) to max(bloomDay).
For each day, greedily count consecutive bloomed flowers to count bouquets.

CPP

int minDays(vector<int>& bloomDay, int m, int k) {
    long long needed = (long long)m * k;
    if (needed > (long long)bloomDay.size()) return -1;

    int lo = *min_element(bloomDay.begin(), bloomDay.end());
    int hi = *max_element(bloomDay.begin(), bloomDay.end());

    auto canMake = [&](int day) -> bool {
        int bouquets = 0, consecutive = 0;
        for (int d : bloomDay) {
            if (d <= day) {
                consecutive++;
                if (consecutive == k) {
                    bouquets++;
                    consecutive = 0;
                }
            } else {
                consecutive = 0;
            }
        }
        return bouquets >= m;
    };

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canMake(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Pattern 8: Capacity to Ship Packages (LC 1011)

CPP

int shipWithinDays(vector<int>& weights, int days) {
    int lo = *max_element(weights.begin(), weights.end());
    int hi = accumulate(weights.begin(), weights.end(), 0);

    auto canShip = [&](int capacity) -> bool {
        int daysNeeded = 1, currentLoad = 0;
        for (int w : weights) {
            if (currentLoad + w > capacity) {
                daysNeeded++;
                currentLoad = w;
            } else {
                currentLoad += w;
            }
        }
        return daysNeeded <= days;
    };

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canShip(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Summary: Binary Search Decision Guide

Common Gotchas:

Off-by-one errors: carefully decide lo <= hi vs lo < hi, and hi = mid vs hi = mid - 1
Integer overflow: always use lo + (hi - lo) / 2
Infinite loops: ensure lo or hi always changes (watch the "find max" template)
Edge cases: empty array, single element, target not present, all elements equal

n! possible permutations of n elements.
A decision tree with k comparisons has at most 2^k leaves.
We need 2^k >= n!  ->  k >= log2(n!)  ->  k >= n log n - n + O(log n) = Omega(n log n).

Non-comparison sorts (counting, radix, bucket) bypass this bound by not using comparisons.

Intuition

Algorithm

Visual Step-by-Step

Complexity Analysis

C++ Code

When to Use

Intuition

Algorithm

Visual Walkthrough

Why Selection Sort is NOT Stable

Complexity Analysis

C++ Code

When to Use

Intuition

Algorithm

Visual Walkthrough

Why Insertion Sort is Excellent for Nearly-Sorted Data

Complexity Analysis

C++ Code

Binary Insertion Sort

When to Use

Intuition: The Divide and Conquer Paradigm

Visual: Split and Merge Phases

The Merge Operation in Detail

Why Merge Sort is Stable

Complexity Analysis

Complete C++ Code

Optimized Merge Sort (with temp buffer reuse)

Bottom-Up (Iterative) Merge Sort

When to Use Merge Sort

Application: Counting Inversions

Intuition

The Partition Step: Two Schemes

Lomuto Partition Scheme

Hoare Partition Scheme

Why O(n^2) Worst Case and How to Avoid It

Three-Way Partition (Dutch National Flag)

Complete Quick Sort with Lomuto + Random Pivot

Complete Quick Sort with Hoare Partition

Tail Recursion Optimization

Complexity Analysis

When to Use

Intuition

Array Representation of a Heap

Heapify Operation

Visual Walkthrough of Heap Sort

Complexity Analysis

C++ Code

When to Use

Intuition

Algorithm

Visual Step-by-Step

Complexity

C++ Code

Limitations

When to Use

Intuition

Algorithm (LSD Radix Sort)

Visual Walkthrough

Complexity

C++ Code

Radix Sort with Base 256 (Byte-level)

When to Use

Intuition

Algorithm

Visual with Uniform Distribution

Complexity

C++ Code

For Integer Bucket Sort

When to Use

Intuition

C++ Code

Sentinel Linear Search

When to Use

Prerequisite

The Core Idea

Visual Walkthrough

Why lo + (hi - lo) / 2 instead of (lo + hi) / 2?

The Three Essential Templates

Complexity

Why `lo + (hi - lo) / 2` instead of `(lo + hi) / 2`?