On this page

Sorting & Searching

Sorting and searching are the workhorses of computer science. Every database query involves sorting or searching. Every recommendation engine ranks (sorts) results. Every time you call Array.prototype.sort() or list.sort(), you are running a carefully engineered sorting algorithm. Understanding these algorithms is not about reimplementing them — it is about knowing their trade-offs so you can choose the right tool, and about mastering binary search, which is arguably the most versatile technique in all of algorithms.

This page is the overview lesson of Module 2 (Searching & Sorting). It shows every major algorithm once — with code in four languages, a hand trace and the key correctness argument — and then points down into the deep lessons where each one gets a full treatment. Read it end to end first; come back to it as the map.

How this module is organised

Module 2 has two halves. The sorting half builds from the simplest quadratic sorts to the hybrids that ship in standard libraries, and ends with the lower bound that explains why non-comparison sorts exist. The searching half starts with binary search — the single most reusable idea in the module — and widens to other search strategies and to selection, which finds one order statistic without sorting at all. The capstone makes you implement and benchmark the sorts side by side.

flowchart TD
    OV["Sorting & Searching (this page)"] --> ES["Elementary Sorts & Stability"]
    ES --> MS["Merge Sort & Inversions"]
    ES --> QS["Quick Sort & Introsort"]
    ES --> HS["Heap Sort"]
    MS --> NC["Non-Comparison Sorts & the Lower Bound"]
    QS --> NC
    HS --> NC
    NC --> RW["Sorting in the Real World"]
    OV --> BS["Binary Search Mastery"]
    BS --> OS["Other Searches"]
    QS --> QSel["Quickselect & Order Statistics"]
    OS --> QSel
    RW --> CAP["Capstone: Sorting Library"]
    QSel --> CAP
LessonWhat it adds beyond this overview
Module 2 indexStudy order, time budget per lesson, and how the pieces fit
Elementary Sorts & StabilityBubble, selection, insertion and Shell sort; inversions; what stability means and when it matters
Merge Sort & Inversion CountingTop-down and bottom-up merge sort, the recurrence, counting inversions during the merge, external sorting
Quick Sort, Partition Schemes & IntrosortLomuto vs Hoare vs three-way partition, the expected comparison proof, introsort and pdqsort
Heap Sort heap construction, sift-down vs sift-up, why heap sort is in place and guaranteed but cache-unfriendly
Non-Comparison Sorts & the Lower BoundThe decision-tree proof in full, counting, radix (LSD and MSD) and bucket sort
Sorting in the Real WorldTimsort and Powersort, dual-pivot quicksort, comparators, stability guarantees per language, external and parallel sorting
Binary Search MasteryOne template for every variant, lower and upper bound, binary search on the answer, on real numbers, and on monotone predicates
Other SearchesTernary search on unimodal functions, exponential search for unbounded input, interpolation search, meet-in-the-middle
Quickselect & Order Statistics-th smallest in expected and worst-case , median of medians, top- in streams, order-statistic trees
Capstone: A Sorting Library With BenchmarksImplement five sorts behind one interface, stress-test them, and benchmark them on four input shapes

Prerequisites: Complexity Analysis for recurrences such as , Recursion & Mathematical Induction for the correctness proofs, and Arrays & Strings for two pointers, which is what a merge and a partition really are. After this module, Module 3 · Trees generalises binary search into binary search trees.

Pattern triggers

Sorting is rarely the answer to an interview problem; it is the preprocessing step that makes a simple answer possible. Binary search is rarely announced; it hides behind words like "minimum" and "at least". Scan for these signals.

If the problem says… / has…Think ofWhy
"sorted array", "find target", "first / last position", "insert position"Binary search (lower / upper bound)Sortedness makes "is the answer left or right of mid?" decidable in one comparison
"minimum capacity / speed / time such that…", "maximise the minimum", "at least / at most"Binary search on the answerFeasibility is monotone: if works, every larger works too
"rotated sorted array", "peak", "bitonic"Modified binary searchAt least one half is still ordered, so half the range can be discarded
"pairs / triplets with sum …", "closest pair", "remove duplicates"Sort + two pointersAfter sorting, moving a pointer rules out a whole set of candidates
"merge intervals", "meeting rooms", "schedule", "overlapping"Sort by start (or end) + sweepSorting makes overlap a question about neighbours only
"-th largest", "median", "top "Quickselect / heap, not a full sortOnly one position (or items) matter
"values in a small range", "ages", "scores 0–100", "digits", "characters"Counting sort / bucket by valueLinear time beats the comparison lower bound
"count inversions", "how many smaller elements to the right"Merge sort with countingInversions across halves are counted in bulk during the merge
"group anagrams", "canonical form"Sort each item as a keySorting is a normal form: equal multisets sort to equal strings
"custom order", "largest number from digits", "sort by frequency then value"Custom comparatorThe problem is defining a total order; the sort is free
"nearly sorted", "each element at most from its place"Insertion sort or a heap of size Work proportional to disorder, or
"data does not fit in memory", "sort a 100 GB file"External merge sortSequential runs plus a -way merge with a heap

When "sorted" appears in the input, binary search or two pointers is almost always intended. When "sorted" does not appear but the brute force is over pairs, ask whether sorting first () turns the pair search into a linear sweep.

Sorting Algorithms Overview

AlgorithmBestAverageWorstSpaceStable?In-Place?
Bubble SortYesYes
Selection SortNoYes
Insertion SortYesYes
Merge SortYesNo
Quick SortNoYes
Heap SortNoYes
Counting SortYesNo
Radix SortYesNo

= range of values, = number of digits.

When to Use Which

  • Nearly sorted data: Insertion sort ( best case)
  • General purpose: Merge sort (guaranteed , stable)
  • In-place, general purpose: Quicksort (fastest in practice for random data)
  • Integer data with known range: Counting sort or radix sort ()
  • External sorting (data doesn't fit in memory): Merge sort (sequential access pattern)
  • Priority queue operations: Heap sort or partial sorting with a heap

Reading the comparison: stability, adaptivity, in-place, worst case

Big-O columns hide the properties that usually decide which sort you want. Four of them matter most.

  • Stable means elements with equal keys keep their original relative order. It matters whenever you sort records by one field after another: sort orders by date, then stably by customer, and each customer's orders stay in date order. Every language's "sort objects" routine is stable for this reason.
  • Adaptive means the algorithm runs faster on input that is already partly ordered. Real data is rarely random — log files arrive almost in time order, a leaderboard changes a few entries between updates — so adaptivity is worth more in practice than a better constant on random input.
  • In-place means extra memory (or for a recursion stack, by the usual convention). It matters for huge arrays and for embedded or kernel code that cannot allocate.
  • Worst case matters when inputs can be chosen by an adversary (a web service sorting user-supplied data) or when latency must be bounded. "Fast on average" is a property of your data; "fast in the worst case" is a property of the algorithm.
AlgorithmComparisons, worst caseStableAdaptiveExtra spaceWhat triggers the worst caseWhere it is used
Bubble (with early exit)YesYes: one pass on sorted inputReversed inputTeaching only
Selection alwaysNo (swap version)NoEvery inputWhen writes are expensive: at most swaps
InsertionYesYes: Reversed inputSmall arrays, and the base case of every hybrid sort
Shell sortDepends on the gap sequence; for Knuth's gapsNoSomewhatGap-dependentSmall or embedded C libraries that want no recursion
Merge (top-down)about YesOnly with a "halves already ordered" check or run detectionNone ( always)Linked lists, external sorting, stable library sorts
Quick (random pivot)NoNo stack if recursing on the smaller sideRepeated bad pivots: sorted input with a fixed pivot; many duplicates with a two-way partitionPrimitive-array sorts, as the core of introsort / pdqsort
Heapabout NoNoNone ( always)Introsort's fallback; the Linux kernel's sort()
IntrosortNoNoNone (heap sort caps it)C++ std::sort (libstdc++, MSVC)
Timsort / PowersortYesYes: on sorted or reversed input, fast on few runsNonePython, Java objects, V8, Android
Countingnone (no comparisons)Yes (prefix-sum version)NoHuge value range Small integer keys; radix sort's inner pass
Radix (LSD)noneYesNo for base Long keys (many digits)Fixed-width integers, GPU sorting, suffix arrays

Two rules of thumb fall out of this table. First, there is no comparison sort that is simultaneously stable, in place, and worst case in a simple form: merge sort gives up in-place, heap sort and quicksort give up stability. Second, the libraries that ship today are all hybrids: they use insertion sort for small ranges, a fast method for the bulk, and a fallback or a run detector to fix that method's weakness.

Merge Sort

Divide the array in half, recursively sort each half, then merge the sorted halves. The merge step is the key insight — merging two sorted arrays takes time.

graph TD
    A["[38, 27, 43, 3, 9, 82, 10]"] --> B["[38, 27, 43, 3]"]
    A --> C["[9, 82, 10]"]
    B --> D["[38, 27]"]
    B --> E["[43, 3]"]
    C --> F["[9, 82]"]
    C --> G["[10]"]
    D --> H["[27, 38]"]
    E --> I["[3, 43]"]
    F --> J["[9, 82]"]
    G --> K["[10]"]
    H --> L["[3, 27, 38, 43]"]
    I --> L
    J --> M["[9, 10, 82]"]
    K --> M
    L --> N["[3, 9, 10, 27, 38, 43, 82]"]
    M --> N
def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left: list[int], right: list[int]) -> list[int]:
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result


# --- self-check (same data in all four languages) ---
assert merge_sort([38, 27, 43, 3, 9, 82, 10]) == [3, 9, 10, 27, 38, 43, 82]
assert merge_sort([5, 3, 8, 4, 2]) == [2, 3, 4, 5, 8]
assert merge_sort([]) == []
assert merge_sort([1]) == [1]
assert merge_sort([2, 1, 2, 1, -3]) == [-3, 1, 1, 2, 2]
print("merge_sort OK")
import java.util.Arrays;

public class MergeSort {
    static int[] mergeSort(int[] arr) {
        if (arr.length <= 1) return arr;
        int mid = arr.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
        return merge(left, right);
    }

    static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) result[k++] = left[i++];   // <= keeps it stable
            else result[k++] = right[j++];
        }
        while (i < left.length) result[k++] = left[i++];
        while (j < right.length) result[k++] = right[j++];
        return result;
    }

    static void check(int[] got, int[] want) {
        if (!Arrays.equals(got, want)) throw new AssertionError(Arrays.toString(got));
    }

    public static void main(String[] args) {
        check(mergeSort(new int[]{38, 27, 43, 3, 9, 82, 10}), new int[]{3, 9, 10, 27, 38, 43, 82});
        check(mergeSort(new int[]{5, 3, 8, 4, 2}), new int[]{2, 3, 4, 5, 8});
        check(mergeSort(new int[]{}), new int[]{});
        check(mergeSort(new int[]{1}), new int[]{1});
        check(mergeSort(new int[]{2, 1, 2, 1, -3}), new int[]{-3, 1, 1, 2, 2});
        System.out.println("mergeSort OK");
    }
}
#include <cassert>
#include <iostream>
#include <vector>

std::vector<int> merge(const std::vector<int>& left, const std::vector<int>& right) {
    std::vector<int> result;
    result.reserve(left.size() + right.size());
    std::size_t i = 0, j = 0;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) result.push_back(left[i++]);  // <= keeps it stable
        else result.push_back(right[j++]);
    }
    result.insert(result.end(), left.begin() + i, left.end());
    result.insert(result.end(), right.begin() + j, right.end());
    return result;
}

std::vector<int> mergeSort(const std::vector<int>& arr) {
    if (arr.size() <= 1) return arr;
    std::size_t mid = arr.size() / 2;
    std::vector<int> left = mergeSort(std::vector<int>(arr.begin(), arr.begin() + mid));
    std::vector<int> right = mergeSort(std::vector<int>(arr.begin() + mid, arr.end()));
    return merge(left, right);
}

int main() {
    assert((mergeSort({38, 27, 43, 3, 9, 82, 10}) == std::vector<int>{3, 9, 10, 27, 38, 43, 82}));
    assert((mergeSort({5, 3, 8, 4, 2}) == std::vector<int>{2, 3, 4, 5, 8}));
    assert(mergeSort({}).empty());
    assert((mergeSort({1}) == std::vector<int>{1}));
    assert((mergeSort({2, 1, 2, 1, -3}) == std::vector<int>{-3, 1, 1, 2, 2}));
    std::cout << "mergeSort OK\n";
}
import assert from "node:assert/strict";

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i), right.slice(j));
}

// --- self-check ---
assert.deepEqual(mergeSort([38, 27, 43, 3, 9, 82, 10]), [3, 9, 10, 27, 38, 43, 82]);
assert.deepEqual(mergeSort([5, 3, 8, 4, 2]), [2, 3, 4, 5, 8]);
assert.deepEqual(mergeSort([]), []);
assert.deepEqual(mergeSort([1]), [1]);
assert.deepEqual(mergeSort([2, 1, 2, 1, -3]), [-3, 1, 1, 2, 2]);
console.log("mergeSort OK");

Complexity: time always. space for the temporary arrays. Stable.

Why merge sort matters in production: It is the basis of external sorting (sorting data that doesn't fit in RAM). The merge step only needs sequential access, making it efficient for disk I/O. TimSort (Python's list.sort(), Java's Arrays.sort() for objects) is a hybrid of merge sort and insertion sort.

Trace: merging two sorted halves

The last merge in the diagram above combines left = [3, 27, 38, 43] and right = [9, 10, 82]. Each row is one iteration of the while loop (computed by script).

StepijCompareTakeresult after
1003 vs 93 (left)[3]
21027 vs 99 (right)[3, 9]
31127 vs 1010 (right)[3, 9, 10]
41227 vs 8227 (left)[3, 9, 10, 27]
52238 vs 8238 (left)[3, 9, 10, 27, 38]
63243 vs 8243 (left)[3, 9, 10, 27, 38, 43]
—42left exhaustedcopy rest of right[3, 9, 10, 27, 38, 43, 82]

Six comparisons for seven elements. A merge of sizes and makes at most comparisons, and as few as when one side is entirely smaller.

Why merge sort is correct and why it is

Merge invariant. Before each iteration, result holds the i + j smallest elements of left ∪ right in sorted order, and left[i], right[j] are the smallest remaining elements of their arrays. The smaller of those two is therefore the smallest remaining element overall, so appending it preserves the invariant. When one array is exhausted, the rest of the other is already sorted and no smaller than everything in result. Taking from left on ties (<=) is exactly what makes the sort stable.

Sort correctness follows by strong induction on the length: arrays of length 0 or 1 are sorted; for longer arrays the two recursive calls return sorted halves by the induction hypothesis, and the merge of two sorted arrays is sorted.

Cost. . The recursion tree has levels and each level merges a total of elements, so . The Merge Sort lesson derives the exact comparison count and shows the bottom-up version, which needs no recursion at all.

Quick Sort

Choose a pivot, partition the array so everything less than the pivot is on the left and everything greater is on the right, then recursively sort each side.

import random

def quick_sort(arr: list[int], lo: int = 0, hi: int | None = None) -> None:
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return

    pivot_idx = partition(arr, lo, hi)
    quick_sort(arr, lo, pivot_idx - 1)
    quick_sort(arr, pivot_idx + 1, hi)

def partition(arr: list[int], lo: int, hi: int) -> int:
    # Randomized pivot to avoid worst-case on sorted input
    rand_idx = random.randint(lo, hi)
    arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx]

    pivot = arr[hi]
    i = lo - 1

    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1


# --- self-check (same data in all four languages) ---
for data, want in [([7, 2, 9, 4, 3, 8, 6], [2, 3, 4, 6, 7, 8, 9]),
                   ([5, 3, 8, 4, 2], [2, 3, 4, 5, 8]),
                   ([], []), ([1], [1]),
                   ([3, -1, 2, -1, 0], [-1, -1, 0, 2, 3])]:
    a = list(data)
    quick_sort(a)
    assert a == want, (data, a)
big = list(range(2000, 0, -1))
quick_sort(big)
assert big == list(range(1, 2001))
print("quick_sort OK")
import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    static final Random RNG = new Random(42);

    static void quickSort(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);
    }

    static int partition(int[] arr, int lo, int hi) {
        swap(arr, lo + RNG.nextInt(hi - lo + 1), hi);   // randomized pivot
        int pivot = arr[hi];
        int i = lo - 1;
        for (int j = lo; j < hi; j++) {
            if (arr[j] <= pivot) swap(arr, ++i, j);
        }
        swap(arr, i + 1, hi);
        return i + 1;
    }

    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

    static void check(int[] data, int[] want) {
        int[] a = data.clone();
        quickSort(a, 0, a.length - 1);
        if (!Arrays.equals(a, want)) throw new AssertionError(Arrays.toString(a));
    }

    public static void main(String[] args) {
        check(new int[]{7, 2, 9, 4, 3, 8, 6}, new int[]{2, 3, 4, 6, 7, 8, 9});
        check(new int[]{5, 3, 8, 4, 2}, new int[]{2, 3, 4, 5, 8});
        check(new int[]{}, new int[]{});
        check(new int[]{1}, new int[]{1});
        check(new int[]{3, -1, 2, -1, 0}, new int[]{-1, -1, 0, 2, 3});
        int[] big = new int[2000], want = new int[2000];
        for (int i = 0; i < 2000; i++) { big[i] = 2000 - i; want[i] = i + 1; }
        check(big, want);
        System.out.println("quickSort OK");
    }
}
#include <cassert>
#include <iostream>
#include <random>
#include <utility>
#include <vector>

std::mt19937 rng(42);

int partition(std::vector<int>& arr, int lo, int hi) {
    std::uniform_int_distribution<int> pick(lo, hi);
    std::swap(arr[pick(rng)], arr[hi]);                 // randomized pivot
    int pivot = arr[hi];
    int i = lo - 1;
    for (int j = lo; j < hi; ++j) {
        if (arr[j] <= pivot) std::swap(arr[++i], arr[j]);
    }
    std::swap(arr[i + 1], arr[hi]);
    return i + 1;
}

void quickSort(std::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 check(std::vector<int> a, const std::vector<int>& want) {
    quickSort(a, 0, static_cast<int>(a.size()) - 1);
    assert(a == want);
}

int main() {
    check({7, 2, 9, 4, 3, 8, 6}, {2, 3, 4, 6, 7, 8, 9});
    check({5, 3, 8, 4, 2}, {2, 3, 4, 5, 8});
    check({}, {});
    check({1}, {1});
    check({3, -1, 2, -1, 0}, {-1, -1, 0, 2, 3});
    std::vector<int> big(2000), want(2000);
    for (int i = 0; i < 2000; ++i) { big[i] = 2000 - i; want[i] = i + 1; }
    check(big, want);
    std::cout << "quickSort OK\n";
}
import assert from "node:assert/strict";

function quickSort(arr: number[], lo = 0, hi = arr.length - 1): void {
  if (lo >= hi) return;

  const pivot = partition(arr, lo, hi);
  quickSort(arr, lo, pivot - 1);
  quickSort(arr, pivot + 1, hi);
}

function partition(arr: number[], lo: number, hi: number): number {
  const pivot = arr[hi]; // last element as pivot
  let i = lo - 1;

  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }

  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

// --- self-check ---
const cases: [number[], number[]][] = [
  [[7, 2, 9, 4, 3, 8, 6], [2, 3, 4, 6, 7, 8, 9]],
  [[5, 3, 8, 4, 2], [2, 3, 4, 5, 8]],
  [[], []], [[1], [1]],
  [[3, -1, 2, -1, 0], [-1, -1, 0, 2, 3]],
];
for (const [data, want] of cases) {
  const a = data.slice();
  quickSort(a);
  assert.deepEqual(a, want);
}
// Last-element pivot on reversed input is the O(n^2) worst case; 2000 elements is still fast.
const big = Array.from({ length: 2000 }, (_, i) => 2000 - i);
quickSort(big);
assert.deepEqual(big, Array.from({ length: 2000 }, (_, i) => i + 1));
console.log("quickSort OK");

Complexity: average, worst case (when pivot is always min/max). stack space. Not stable.

Correction

The stack bound holds only if the implementation recurses into the smaller side and loops on the larger one. The version above recurses into both sides, so a run of bad pivots can nest calls deep: stack in the worst case, which overflows the default stack for large sorted inputs in the TypeScript version (fixed last-element pivot). Introsort and the capstone use the smaller-side-first loop.

WARNING

Quicksort's worst case occurs on already-sorted data when the pivot is the first or last element. Always use randomized pivot selection or median-of-three to avoid this in production.

Trace: one Lomuto partition

arr = [7, 2, 9, 4, 3, 8, 6], pivot = last element = 6, i starts at lo - 1 = -1. Each row is one iteration of the for loop (computed by script).

jarr[j]arr[j] <= 6?Actioni afterArray after
07no—-1[7, 2, 9, 4, 3, 8, 6]
12yesswap arr[0], arr[1]0[2, 7, 9, 4, 3, 8, 6]
29no—0[2, 7, 9, 4, 3, 8, 6]
34yesswap arr[1], arr[3]1[2, 4, 9, 7, 3, 8, 6]
43yesswap arr[2], arr[4]2[2, 4, 3, 7, 9, 8, 6]
58no—2[2, 4, 3, 7, 9, 8, 6]
endswap arr[3], arr[6] (pivot into place)[2, 4, 3, 6, 9, 8, 7]

The pivot lands at index 3, which is its final sorted position: three elements are smaller. Quicksort now recurses on [2, 4, 3] and [9, 8, 7].

Why partition is correct

Invariant. At the start of each iteration, arr[lo..i] holds elements pivot, arr[i+1..j-1] holds elements pivot, and arr[j..hi-1] is unexamined. Examining arr[j] either leaves it in the "greater" block (if it is greater) or swaps it with the first element of the "greater" block and grows the "smaller" block by one. When j reaches hi, only two blocks remain, and swapping the pivot into position i + 1 puts it between them. Quicksort is then correct by strong induction: the pivot is in its final place, and each side is sorted by the recursive calls.

Why the average is . With a random pivot, elements (the -th and -th smallest) are compared only if one of them is the first pivot chosen from , which happens with probability . Summing over all pairs gives about expected comparisons — about 39% more than merge sort, but with sequential memory access, no auxiliary array and a tight inner loop, which is why quicksort is usually faster anyway. Quick Sort has the full proof.

Quick Select (Kth Smallest Element)

A modified quicksort that only recurses into the partition containing the target index. Expected time.

import random

def partition(arr: list[int], lo: int, hi: int) -> int:
    rand_idx = random.randint(lo, hi)
    arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx]
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

def quick_select(arr: list[int], k: int) -> int:
    """Find the kth smallest element (0-indexed)."""
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        pivot_idx = partition(arr, lo, hi)
        if pivot_idx == k:
            return arr[k]
        elif pivot_idx < k:
            lo = pivot_idx + 1
        else:
            hi = pivot_idx - 1

    return arr[lo]


# --- self-check (same data in all four languages) ---
assert quick_select([3, 2, 1, 5, 6, 4], 4) == 5        # 2nd largest = index n-2
assert quick_select([7, 2, 9, 4, 3, 8, 6], 3) == 6     # the median
assert quick_select([5], 0) == 5
assert quick_select([2, 2, 1, 1], 1) == 1
print("quick_select OK")
import java.util.Random;

public class QuickSelect {
    static final Random RNG = new Random(42);

    static int partition(int[] arr, int lo, int hi) {
        swap(arr, lo + RNG.nextInt(hi - lo + 1), hi);
        int pivot = arr[hi], i = lo - 1;
        for (int j = lo; j < hi; j++) if (arr[j] <= pivot) swap(arr, ++i, j);
        swap(arr, i + 1, hi);
        return i + 1;
    }

    /** kth smallest, 0-indexed. Expected O(n). Reorders arr. */
    static int quickSelect(int[] arr, int k) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int p = partition(arr, lo, hi);
            if (p == k) return arr[k];
            if (p < k) lo = p + 1;
            else hi = p - 1;
        }
        return arr[lo];
    }

    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

    static void check(boolean ok, String m) { if (!ok) throw new AssertionError(m); }

    public static void main(String[] args) {
        check(quickSelect(new int[]{3, 2, 1, 5, 6, 4}, 4) == 5, "t1");
        check(quickSelect(new int[]{7, 2, 9, 4, 3, 8, 6}, 3) == 6, "t2");
        check(quickSelect(new int[]{5}, 0) == 5, "t3");
        check(quickSelect(new int[]{2, 2, 1, 1}, 1) == 1, "t4");
        System.out.println("quickSelect OK");
    }
}
#include <cassert>
#include <iostream>
#include <random>
#include <utility>
#include <vector>

std::mt19937 rng(42);

int partition(std::vector<int>& arr, int lo, int hi) {
    std::uniform_int_distribution<int> pick(lo, hi);
    std::swap(arr[pick(rng)], arr[hi]);
    int pivot = arr[hi], i = lo - 1;
    for (int j = lo; j < hi; ++j) if (arr[j] <= pivot) std::swap(arr[++i], arr[j]);
    std::swap(arr[i + 1], arr[hi]);
    return i + 1;
}

// kth smallest, 0-indexed. Expected O(n). Takes a copy, so the caller's vector is untouched.
int quickSelect(std::vector<int> arr, int k) {
    int lo = 0, hi = static_cast<int>(arr.size()) - 1;
    while (lo <= hi) {
        int p = partition(arr, lo, hi);
        if (p == k) return arr[k];
        if (p < k) lo = p + 1;
        else hi = p - 1;
    }
    return arr[lo];
}

int main() {
    assert(quickSelect({3, 2, 1, 5, 6, 4}, 4) == 5);
    assert(quickSelect({7, 2, 9, 4, 3, 8, 6}, 3) == 6);
    assert(quickSelect({5}, 0) == 5);
    assert(quickSelect({2, 2, 1, 1}, 1) == 1);
    std::cout << "quickSelect OK\n";
}
import assert from "node:assert/strict";

function partition(arr: number[], lo: number, hi: number): number {
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [arr[r], arr[hi]] = [arr[hi], arr[r]];
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

/** kth smallest, 0-indexed. Expected O(n). Reorders arr. */
function quickSelect(arr: number[], k: number): number {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const p = partition(arr, lo, hi);
    if (p === k) return arr[k];
    if (p < k) lo = p + 1;
    else hi = p - 1;
  }
  return arr[lo];
}

assert.equal(quickSelect([3, 2, 1, 5, 6, 4], 4), 5);
assert.equal(quickSelect([7, 2, 9, 4, 3, 8, 6], 3), 6);
assert.equal(quickSelect([5], 0), 5);
assert.equal(quickSelect([2, 2, 1, 1], 1), 1);
console.log("quickSelect OK");

Complexity: expected, worst case. Use median-of-medians for guaranteed .

The expected-linear proof, median of medians (and why it needs groups of five), introselect, streaming top- and order-statistic trees are all in Quickselect, Median of Medians & Order Statistics.

Heap Sort

Build a max-heap from the array, then repeatedly extract the maximum element.

def heap_sort(arr: list[int]) -> None:
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

def heapify(arr: list[int], heap_size: int, root: int) -> None:
    largest = root
    left = 2 * root + 1
    right = 2 * root + 2

    if left < heap_size and arr[left] > arr[largest]:
        largest = left
    if right < heap_size and arr[right] > arr[largest]:
        largest = right

    if largest != root:
        arr[root], arr[largest] = arr[largest], arr[root]
        heapify(arr, heap_size, largest)


# --- self-check (same data in all four languages) ---
for data, want in [([12, 11, 13, 5, 6, 7], [5, 6, 7, 11, 12, 13]),
                   ([5, 3, 8, 4, 2], [2, 3, 4, 5, 8]),
                   ([], []), ([1], [1]),
                   ([3, -1, 2, -1, 0], [-1, -1, 0, 2, 3])]:
    a = list(data)
    heap_sort(a)
    assert a == want, (data, a)
print("heap_sort OK")
import java.util.Arrays;

public class HeapSort {
    static void heapSort(int[] arr) {
        int n = arr.length;
        for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);     // build max-heap
        for (int i = n - 1; i > 0; i--) {
            int t = arr[0]; arr[0] = arr[i]; arr[i] = t;              // move max to end
            heapify(arr, i, 0);
        }
    }

    static void heapify(int[] arr, int heapSize, int root) {
        while (true) {                                                 // iterative sift-down
            int largest = root, left = 2 * root + 1, right = 2 * root + 2;
            if (left < heapSize && arr[left] > arr[largest]) largest = left;
            if (right < heapSize && arr[right] > arr[largest]) largest = right;
            if (largest == root) return;
            int t = arr[root]; arr[root] = arr[largest]; arr[largest] = t;
            root = largest;
        }
    }

    static void check(int[] data, int[] want) {
        int[] a = data.clone();
        heapSort(a);
        if (!Arrays.equals(a, want)) throw new AssertionError(Arrays.toString(a));
    }

    public static void main(String[] args) {
        check(new int[]{12, 11, 13, 5, 6, 7}, new int[]{5, 6, 7, 11, 12, 13});
        check(new int[]{5, 3, 8, 4, 2}, new int[]{2, 3, 4, 5, 8});
        check(new int[]{}, new int[]{});
        check(new int[]{1}, new int[]{1});
        check(new int[]{3, -1, 2, -1, 0}, new int[]{-1, -1, 0, 2, 3});
        System.out.println("heapSort OK");
    }
}
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>

void heapify(std::vector<int>& arr, int heapSize, int root) {
    while (true) {                                                 // iterative sift-down
        int largest = root, left = 2 * root + 1, right = 2 * root + 2;
        if (left < heapSize && arr[left] > arr[largest]) largest = left;
        if (right < heapSize && arr[right] > arr[largest]) largest = right;
        if (largest == root) return;
        std::swap(arr[root], arr[largest]);
        root = largest;
    }
}

void heapSort(std::vector<int>& arr) {
    int n = static_cast<int>(arr.size());
    for (int i = n / 2 - 1; i >= 0; --i) heapify(arr, n, i);     // build max-heap
    for (int i = n - 1; i > 0; --i) {
        std::swap(arr[0], arr[i]);                                // move max to end
        heapify(arr, i, 0);
    }
}

void check(std::vector<int> a, const std::vector<int>& want) {
    heapSort(a);
    assert(a == want);
}

int main() {
    check({12, 11, 13, 5, 6, 7}, {5, 6, 7, 11, 12, 13});
    check({5, 3, 8, 4, 2}, {2, 3, 4, 5, 8});
    check({}, {});
    check({1}, {1});
    check({3, -1, 2, -1, 0}, {-1, -1, 0, 2, 3});
    std::cout << "heapSort OK\n";
}
import assert from "node:assert/strict";

function heapSort(arr: number[]): void {
  const n = arr.length;

  // Build max-heap
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }

  // Extract elements from heap one by one
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]]; // move max to end
    heapify(arr, i, 0);
  }
}

function heapify(arr: number[], heapSize: number, rootIdx: number): void {
  let largest = rootIdx;
  const left = 2 * rootIdx + 1;
  const right = 2 * rootIdx + 2;

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

  if (largest !== rootIdx) {
    [arr[rootIdx], arr[largest]] = [arr[largest], arr[rootIdx]];
    heapify(arr, heapSize, largest);
  }
}

// --- self-check ---
const heapCases: [number[], number[]][] = [
  [[12, 11, 13, 5, 6, 7], [5, 6, 7, 11, 12, 13]],
  [[5, 3, 8, 4, 2], [2, 3, 4, 5, 8]],
  [[], []], [[1], [1]],
  [[3, -1, 2, -1, 0], [-1, -1, 0, 2, 3]],
];
for (const [data, want] of heapCases) {
  const a = data.slice();
  heapSort(a);
  assert.deepEqual(a, want);
}
console.log("heapSort OK");

Complexity: always. space. Not stable. See Heaps & Priority Queues for more.

Two facts make heap sort more interesting than its table row. The build phase — calling heapify from index down to 0 — is , not , because most nodes sit near the bottom of the heap and sift down only a level or two (the sum converges to ). And heap sort is the standard fallback inside introsort precisely because it has no bad inputs and needs no extra memory, even though its scattered memory access makes it slower than quicksort on average. Heap Sort proves both.

Non-Comparison Sorts

These break the lower bound for comparison-based sorting by exploiting properties of the data.

Counting Sort

For integers in a known range . Count occurrences, then reconstruct.

def counting_sort(arr: list[int]) -> list[int]:
    if not arr:
        return []

    max_val = max(arr)
    count = [0] * (max_val + 1)

    for num in arr:
        count[num] += 1

    result = []
    for val, cnt in enumerate(count):
        result.extend([val] * cnt)

    return result


# --- self-check (same data in all four languages) ---
assert counting_sort([4, 2, 2, 8, 3, 3, 1]) == [1, 2, 2, 3, 3, 4, 8]
assert counting_sort([]) == []
assert counting_sort([0]) == [0]
assert counting_sort([5, 0, 5, 0]) == [0, 0, 5, 5]
print("counting_sort OK")
import java.util.Arrays;

public class CountingSort {
    /** Non-negative integers only; O(n + k) where k = max value. */
    static int[] countingSort(int[] arr) {
        if (arr.length == 0) return new int[0];
        int maxVal = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[maxVal + 1];
        for (int num : arr) count[num]++;
        int[] result = new int[arr.length];
        int k = 0;
        for (int val = 0; val <= maxVal; val++)
            for (int c = 0; c < count[val]; c++) result[k++] = val;
        return result;
    }

    static void check(int[] got, int[] want) {
        if (!Arrays.equals(got, want)) throw new AssertionError(Arrays.toString(got));
    }

    public static void main(String[] args) {
        check(countingSort(new int[]{4, 2, 2, 8, 3, 3, 1}), new int[]{1, 2, 2, 3, 3, 4, 8});
        check(countingSort(new int[]{}), new int[]{});
        check(countingSort(new int[]{0}), new int[]{0});
        check(countingSort(new int[]{5, 0, 5, 0}), new int[]{0, 0, 5, 5});
        System.out.println("countingSort OK");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

// Non-negative integers only; O(n + k) where k = max value.
std::vector<int> countingSort(const std::vector<int>& arr) {
    if (arr.empty()) return {};
    int maxVal = *std::max_element(arr.begin(), arr.end());
    std::vector<int> count(maxVal + 1, 0);
    for (int num : arr) ++count[num];
    std::vector<int> result;
    result.reserve(arr.size());
    for (int val = 0; val <= maxVal; ++val) result.insert(result.end(), count[val], val);
    return result;
}

int main() {
    assert((countingSort({4, 2, 2, 8, 3, 3, 1}) == std::vector<int>{1, 2, 2, 3, 3, 4, 8}));
    assert(countingSort({}).empty());
    assert((countingSort({0}) == std::vector<int>{0}));
    assert((countingSort({5, 0, 5, 0}) == std::vector<int>{0, 0, 5, 5}));
    std::cout << "countingSort OK\n";
}
import assert from "node:assert/strict";

/** Non-negative integers only; O(n + k) where k = max value. */
function countingSort(arr: number[]): number[] {
  if (arr.length === 0) return [];
  const maxVal = Math.max(...arr);
  const count = new Array<number>(maxVal + 1).fill(0);
  for (const num of arr) count[num]++;
  const result: number[] = [];
  count.forEach((cnt, val) => {
    for (let c = 0; c < cnt; c++) result.push(val);
  });
  return result;
}

assert.deepEqual(countingSort([4, 2, 2, 8, 3, 3, 1]), [1, 2, 2, 3, 3, 4, 8]);
assert.deepEqual(countingSort([]), []);
assert.deepEqual(countingSort([0]), [0]);
assert.deepEqual(countingSort([5, 0, 5, 0]), [0, 0, 5, 5]);
console.log("countingSort OK");

Complexity: time and space. Efficient when .

This version reconstructs values from their counts, which only works when the keys are the values. To sort records by an integer key (and to be stable, which radix sort needs), turn the counts into starting positions with a prefix sum and then place each record at start[key]++ in input order; the radix-sort code below does exactly that per digit. Negative keys need an offset: count x - min(arr) instead of x.

Radix Sort

Sort by each digit position, from least significant to most significant, using a stable sort (like counting sort) at each level.

def radix_sort(arr: list[int]) -> list[int]:
    if not arr:
        return []

    max_val = max(arr)
    exp = 1

    while max_val // exp > 0:
        arr = counting_sort_by_digit(arr, exp)
        exp *= 10

    return arr

def counting_sort_by_digit(arr: list[int], exp: int) -> list[int]:
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1

    return output


# --- self-check (same data in all four languages) ---
assert radix_sort([170, 45, 75, 90, 802, 24, 2, 66]) == [2, 24, 45, 66, 75, 90, 170, 802]
assert radix_sort([]) == []
assert radix_sort([0, 0, 1]) == [0, 0, 1]
assert radix_sort([1000, 1, 100, 10]) == [1, 10, 100, 1000]
print("radix_sort OK")
import java.util.Arrays;

public class RadixSort {
    /** LSD radix sort, base 10, non-negative integers. */
    static int[] radixSort(int[] arr) {
        if (arr.length == 0) return new int[0];
        int maxVal = Arrays.stream(arr).max().getAsInt();
        int[] a = arr.clone();
        for (long exp = 1; maxVal / exp > 0; exp *= 10) a = countingSortByDigit(a, (int) exp);
        return a;
    }

    static int[] countingSortByDigit(int[] arr, int exp) {
        int[] output = new int[arr.length];
        int[] count = new int[10];
        for (int num : arr) count[(num / exp) % 10]++;
        for (int i = 1; i < 10; i++) count[i] += count[i - 1];
        for (int i = arr.length - 1; i >= 0; i--) {            // backwards keeps it stable
            int digit = (arr[i] / exp) % 10;
            output[--count[digit]] = arr[i];
        }
        return output;
    }

    static void check(int[] got, int[] want) {
        if (!Arrays.equals(got, want)) throw new AssertionError(Arrays.toString(got));
    }

    public static void main(String[] args) {
        check(radixSort(new int[]{170, 45, 75, 90, 802, 24, 2, 66}), new int[]{2, 24, 45, 66, 75, 90, 170, 802});
        check(radixSort(new int[]{}), new int[]{});
        check(radixSort(new int[]{0, 0, 1}), new int[]{0, 0, 1});
        check(radixSort(new int[]{1000, 1, 100, 10}), new int[]{1, 10, 100, 1000});
        System.out.println("radixSort OK");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

std::vector<int> countingSortByDigit(const std::vector<int>& arr, long long exp) {
    std::vector<int> output(arr.size());
    int count[10] = {};
    for (int num : arr) ++count[(num / exp) % 10];
    for (int i = 1; i < 10; ++i) count[i] += count[i - 1];
    for (int i = static_cast<int>(arr.size()) - 1; i >= 0; --i) {   // backwards keeps it stable
        int digit = static_cast<int>((arr[i] / exp) % 10);
        output[--count[digit]] = arr[i];
    }
    return output;
}

// LSD radix sort, base 10, non-negative integers.
std::vector<int> radixSort(std::vector<int> arr) {
    if (arr.empty()) return arr;
    int maxVal = *std::max_element(arr.begin(), arr.end());
    for (long long exp = 1; maxVal / exp > 0; exp *= 10) arr = countingSortByDigit(arr, exp);
    return arr;
}

int main() {
    assert((radixSort({170, 45, 75, 90, 802, 24, 2, 66}) == std::vector<int>{2, 24, 45, 66, 75, 90, 170, 802}));
    assert(radixSort({}).empty());
    assert((radixSort({0, 0, 1}) == std::vector<int>{0, 0, 1}));
    assert((radixSort({1000, 1, 100, 10}) == std::vector<int>{1, 10, 100, 1000}));
    std::cout << "radixSort OK\n";
}
import assert from "node:assert/strict";

function countingSortByDigit(arr: number[], exp: number): number[] {
  const output = new Array<number>(arr.length);
  const count = new Array<number>(10).fill(0);
  for (const num of arr) count[Math.floor(num / exp) % 10]++;
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];
  for (let i = arr.length - 1; i >= 0; i--) {          // backwards keeps it stable
    const digit = Math.floor(arr[i] / exp) % 10;
    output[--count[digit]] = arr[i];
  }
  return output;
}

/** LSD radix sort, base 10, non-negative integers. */
function radixSort(arr: number[]): number[] {
  if (arr.length === 0) return [];
  const maxVal = Math.max(...arr);
  let a = arr.slice();
  for (let exp = 1; Math.floor(maxVal / exp) > 0; exp *= 10) a = countingSortByDigit(a, exp);
  return a;
}

assert.deepEqual(radixSort([170, 45, 75, 90, 802, 24, 2, 66]), [2, 24, 45, 66, 75, 90, 170, 802]);
assert.deepEqual(radixSort([]), []);
assert.deepEqual(radixSort([0, 0, 1]), [0, 0, 1]);
assert.deepEqual(radixSort([1000, 1, 100, 10]), [1, 10, 100, 1000]);
console.log("radixSort OK");

Complexity: where is the number of digits and is the base (10). For 32-bit integers: .

Why least significant digit first works. After pass , the array is sorted by the last digits. Pass sorts by digit stably, so elements with equal digit keep the order established by the previous passes — which is the order of their last digits. By induction, after passes the array is sorted by all digits. That is why the inner sort must be stable, and why the placement loop runs backwards. Production radix sorts use base 256 (one byte per pass, four passes for 32-bit keys) rather than base 10; the capstone builds one, including the sign-bit trick for negative numbers.

Binary search is the most important searching technique. It works on sorted data and eliminates half the search space on each step.

flowchart TD
    S["lo = 0, hi = n - 1"] --> C{"lo <= hi ?"}
    C -->|"no"| NF["return -1<br/>lo is the insertion point"]
    C -->|"yes"| M["mid = lo + (hi - lo) / 2"]
    M --> E{"nums[mid] vs target"}
    E -->|"equal"| F["return mid"]
    E -->|"less"| L["lo = mid + 1<br/>answer is right of mid"]
    E -->|"greater"| H["hi = mid - 1<br/>answer is left of mid"]
    L --> C
    H --> C
def binary_search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1


# --- self-check (same data in all four languages) ---
nums = [1, 3, 5, 7, 9, 11, 13]
assert binary_search(nums, 7) == 3
assert binary_search(nums, 11) == 5
assert binary_search(nums, 1) == 0 and binary_search(nums, 13) == 6
assert binary_search(nums, 6) == -1
assert binary_search([], 5) == -1
print("binary_search OK")
public class BinarySearch {
    static int binarySearch(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;          // never overflows
            if (nums[mid] == target) return mid;
            if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    static void check(boolean ok, String m) { if (!ok) throw new AssertionError(m); }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 7, 9, 11, 13};
        check(binarySearch(nums, 7) == 3, "t1");
        check(binarySearch(nums, 11) == 5, "t2");
        check(binarySearch(nums, 1) == 0 && binarySearch(nums, 13) == 6, "t3");
        check(binarySearch(nums, 6) == -1, "t4");
        check(binarySearch(new int[]{}, 5) == -1, "t5");
        System.out.println("binarySearch OK");
    }
}
#include <cassert>
#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& nums, int target) {
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;              // never overflows
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    std::vector<int> nums = {1, 3, 5, 7, 9, 11, 13};
    assert(binarySearch(nums, 7) == 3);
    assert(binarySearch(nums, 11) == 5);
    assert(binarySearch(nums, 1) == 0 && binarySearch(nums, 13) == 6);
    assert(binarySearch(nums, 6) == -1);
    assert(binarySearch({}, 5) == -1);
    std::cout << "binarySearch OK\n";
}
import assert from "node:assert/strict";

function binarySearch(nums: number[], target: number): number {
  let lo = 0;
  let hi = nums.length - 1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // avoid overflow
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1; // not found
}

// --- self-check ---
const nums = [1, 3, 5, 7, 9, 11, 13];
assert.equal(binarySearch(nums, 7), 3);
assert.equal(binarySearch(nums, 11), 5);
assert.ok(binarySearch(nums, 1) === 0 && binarySearch(nums, 13) === 6);
assert.equal(binarySearch(nums, 6), -1);
assert.equal(binarySearch([], 5), -1);
console.log("binarySearch OK");

Complexity: time, space.

DANGER

Use lo + (hi - lo) // 2 instead of (lo + hi) // 2 to prevent integer overflow in languages with fixed-size integers (C, C++, Java). In Python and TypeScript this isn't strictly necessary, but it's a good habit.

Trace: binary search, found and not found

nums = [1, 3, 5, 7, 9, 11, 13]. Each row is one loop iteration (computed by script).

Searching for 11:

Iterationlohimidnums[mid]Decision
106377 < 11: lo = 4
246511equal: return 5

Searching for 6 (absent):

Iterationlohimidnums[mid]Decision
106377 > 6: hi = 2
202133 < 6: lo = 2
322255 < 6: lo = 3
end32lo > hi: return -1

The failed search is not wasted: when the loop exits, lo = 3 is exactly the index where 6 would be inserted to keep the array sorted. Python's bisect_left, C++'s std::lower_bound and Java's Arrays.binarySearch (which returns -(insertion point) - 1) all expose this.

The invariant that makes binary search correct

Invariant: if target is in the array, its index is in [lo, hi]. Initially [0, n-1] covers everything. If nums[mid] < target, then because the array is sorted every index ≤ mid holds a value < target, so the target can only be in [mid+1, hi]; symmetrically for >. Each iteration shrinks hi - lo + 1 by at least half (rounding down), so after at most iterations the range is empty or the target is found. For that is 30 iterations.

The deeper view, which Binary Search Mastery builds on: binary search works on any monotone predicate — false, false, …, false, true, …, true — and finds the first true. "nums[i] >= target" is one such predicate; "can_ship(capacity)" below is another. Every variant on this page is the same algorithm with a different predicate.

Binary Search Variations

These variations are where binary search becomes powerful. The key insight: binary search doesn't just find a target — it finds a boundary.

Find Leftmost (First Occurrence)

def find_first(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    result = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            result = mid
            hi = mid - 1          # keep searching left
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result


# --- self-check (same data in all four languages) ---
assert find_first([1, 2, 2, 2, 2, 3, 4], 2) == 1
assert find_first([5, 7, 7, 8, 8, 10], 8) == 3
assert find_first([5, 7, 7, 8, 8, 10], 6) == -1
assert find_first([], 0) == -1
print("find_first OK")
public class FindFirst {
    static int findFirst(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1, result = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) { result = mid; hi = mid - 1; }   // keep searching left
            else if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return result;
    }

    static void check(boolean ok, String m) { if (!ok) throw new AssertionError(m); }

    public static void main(String[] args) {
        check(findFirst(new int[]{1, 2, 2, 2, 2, 3, 4}, 2) == 1, "t1");
        check(findFirst(new int[]{5, 7, 7, 8, 8, 10}, 8) == 3, "t2");
        check(findFirst(new int[]{5, 7, 7, 8, 8, 10}, 6) == -1, "t3");
        check(findFirst(new int[]{}, 0) == -1, "t4");
        System.out.println("findFirst OK");
    }
}
#include <cassert>
#include <iostream>
#include <vector>

int findFirst(const std::vector<int>& nums, int target) {
    int lo = 0, hi = static_cast<int>(nums.size()) - 1, result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) { result = mid; hi = mid - 1; }   // keep searching left
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return result;
}

int main() {
    assert(findFirst({1, 2, 2, 2, 2, 3, 4}, 2) == 1);
    assert(findFirst({5, 7, 7, 8, 8, 10}, 8) == 3);
    assert(findFirst({5, 7, 7, 8, 8, 10}, 6) == -1);
    assert(findFirst({}, 0) == -1);
    std::cout << "findFirst OK\n";
}
import assert from "node:assert/strict";

function findFirst(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;
  let result = -1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) {
      result = mid;
      hi = mid - 1; // keep searching left
    } else if (nums[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  return result;
}

// --- self-check ---
assert.equal(findFirst([1, 2, 2, 2, 2, 3, 4], 2), 1);
assert.equal(findFirst([5, 7, 7, 8, 8, 10], 8), 3);
assert.equal(findFirst([5, 7, 7, 8, 8, 10], 6), -1);
assert.equal(findFirst([], 0), -1);
console.log("findFirst OK");

Trace of findFirst([1, 2, 2, 2, 2, 3, 4], 2) (computed by script). The trick is that a match does not stop the search; it records the index and keeps looking left.

Iterationlohimidnums[mid]Actionresult
10632match: record, hi = 23
20212match: record, hi = 01
300011 < 2: lo = 11
end10lo > hi: return1

Find Rightmost (Last Occurrence)

def find_last(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    result = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            result = mid
            lo = mid + 1          # keep searching right
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result


# --- self-check (same data in all four languages) ---
assert find_last([1, 2, 2, 2, 2, 3, 4], 2) == 4
assert find_last([5, 7, 7, 8, 8, 10], 8) == 4
assert find_last([5, 7, 7, 8, 8, 10], 6) == -1
assert find_last([], 0) == -1
print("find_last OK")
public class FindLast {
    static int findLast(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1, result = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) { result = mid; lo = mid + 1; }   // keep searching right
            else if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return result;
    }

    static void check(boolean ok, String m) { if (!ok) throw new AssertionError(m); }

    public static void main(String[] args) {
        check(findLast(new int[]{1, 2, 2, 2, 2, 3, 4}, 2) == 4, "t1");
        check(findLast(new int[]{5, 7, 7, 8, 8, 10}, 8) == 4, "t2");
        check(findLast(new int[]{5, 7, 7, 8, 8, 10}, 6) == -1, "t3");
        check(findLast(new int[]{}, 0) == -1, "t4");
        System.out.println("findLast OK");
    }
}
#include <cassert>
#include <iostream>
#include <vector>

int findLast(const std::vector<int>& nums, int target) {
    int lo = 0, hi = static_cast<int>(nums.size()) - 1, result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) { result = mid; lo = mid + 1; }   // keep searching right
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return result;
}

int main() {
    assert(findLast({1, 2, 2, 2, 2, 3, 4}, 2) == 4);
    assert(findLast({5, 7, 7, 8, 8, 10}, 8) == 4);
    assert(findLast({5, 7, 7, 8, 8, 10}, 6) == -1);
    assert(findLast({}, 0) == -1);
    std::cout << "findLast OK\n";
}
import assert from "node:assert/strict";

function findLast(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;
  let result = -1;

  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) {
      result = mid;
      lo = mid + 1; // keep searching right
    } else if (nums[mid] < target) {
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }

  return result;
}

// --- self-check ---
assert.equal(findLast([1, 2, 2, 2, 2, 3, 4], 2), 4);
assert.equal(findLast([5, 7, 7, 8, 8, 10], 8), 4);
assert.equal(findLast([5, 7, 7, 8, 8, 10], 6), -1);
assert.equal(findLast([], 0), -1);
console.log("findLast OK");

Together, findFirst and findLast count occurrences in : findLast - findFirst + 1 when the target is present. The standard libraries phrase the same thing as two boundary searches: bisect_left/bisect_right in Python, std::lower_bound/std::upper_bound (or std::equal_range) in C++.

Search in Rotated Sorted Array

def search_rotated(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1

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

        # Determine which half is sorted
        if nums[lo] <= nums[mid]:  # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1

    return -1


# --- self-check (same data in all four languages) ---
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 5) == 1
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 0) == 4
assert search_rotated([4, 5, 6, 7, 0, 1, 2], 3) == -1
assert search_rotated([1], 1) == 0
assert search_rotated([3, 1], 1) == 1
print("search_rotated OK")
public class SearchRotated {
    static int searchRotated(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) {                       // left half is sorted
                if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
                else lo = mid + 1;
            } else {                                           // right half is sorted
                if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
                else hi = mid - 1;
            }
        }
        return -1;
    }

    static void check(boolean ok, String m) { if (!ok) throw new AssertionError(m); }

    public static void main(String[] args) {
        int[] r = {4, 5, 6, 7, 0, 1, 2};
        check(searchRotated(r, 5) == 1, "t1");
        check(searchRotated(r, 0) == 4, "t2");
        check(searchRotated(r, 3) == -1, "t3");
        check(searchRotated(new int[]{1}, 1) == 0, "t4");
        check(searchRotated(new int[]{3, 1}, 1) == 1, "t5");
        System.out.println("searchRotated OK");
    }
}
#include <cassert>
#include <iostream>
#include <vector>

int searchRotated(const std::vector<int>& nums, int target) {
    int lo = 0, hi = static_cast<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 is sorted
            if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
            else lo = mid + 1;
        } else {                                               // right half is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

int main() {
    std::vector<int> r = {4, 5, 6, 7, 0, 1, 2};
    assert(searchRotated(r, 5) == 1);
    assert(searchRotated(r, 0) == 4);
    assert(searchRotated(r, 3) == -1);
    assert(searchRotated({1}, 1) == 0);
    assert(searchRotated({3, 1}, 1) == 1);
    std::cout << "searchRotated OK\n";
}
import assert from "node:assert/strict";

function searchRotated(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] === target) return mid;
    if (nums[lo] <= nums[mid]) {                        // left half is sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {                                            // right half is sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

const r = [4, 5, 6, 7, 0, 1, 2];
assert.equal(searchRotated(r, 5), 1);
assert.equal(searchRotated(r, 0), 4);
assert.equal(searchRotated(r, 3), -1);
assert.equal(searchRotated([1], 1), 0);
assert.equal(searchRotated([3, 1], 1), 1);
console.log("searchRotated OK");

Why it works. A rotated sorted array is two sorted runs. Whichever run mid falls in, the half from lo to mid or from mid to hi lies entirely inside one run and is therefore sorted — and for a sorted half, "is the target inside it?" is a range check on its endpoints. The <= in nums[lo] <= nums[mid] matters when lo == mid (two-element ranges such as [3, 1]). With duplicates the test can fail to tell which half is sorted ([1, 1, 1, 0, 1]), and the worst case degrades to ; see the pitfalls below.

Binary Search on Answer

When you can frame a problem as "what is the minimum/maximum value such that a condition is true?" — binary search on that value.

Example: Minimum Capacity to Ship Packages Within D Days

def ship_within_days(weights: list[int], days: int) -> int:
    def can_ship(capacity: int) -> bool:
        current_load = 0
        needed_days = 1
        for w in weights:
            if current_load + w > capacity:
                needed_days += 1
                current_load = 0
            current_load += w
        return needed_days <= days

    lo = max(weights)       # min possible capacity
    hi = sum(weights)       # max possible capacity

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_ship(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo


# --- self-check (same data in all four languages) ---
assert ship_within_days([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5) == 15
assert ship_within_days([3, 2, 2, 4, 1, 4], 3) == 6
assert ship_within_days([1, 2, 3, 1, 1], 4) == 3
assert ship_within_days([7], 1) == 7
print("ship_within_days OK")
public class ShipWithinDays {
    static boolean canShip(int[] weights, int days, long capacity) {
        long load = 0;
        int needed = 1;
        for (int w : weights) {
            if (load + w > capacity) { needed++; load = 0; }
            load += w;
        }
        return needed <= days;
    }

    static long shipWithinDays(int[] weights, int days) {
        long lo = 0, hi = 0;
        for (int w : weights) { lo = Math.max(lo, w); hi += w; }   // long: sum may exceed int
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (canShip(weights, days, mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }

    static void check(boolean ok, String m) { if (!ok) throw new AssertionError(m); }

    public static void main(String[] args) {
        check(shipWithinDays(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5) == 15, "t1");
        check(shipWithinDays(new int[]{3, 2, 2, 4, 1, 4}, 3) == 6, "t2");
        check(shipWithinDays(new int[]{1, 2, 3, 1, 1}, 4) == 3, "t3");
        check(shipWithinDays(new int[]{7}, 1) == 7, "t4");
        System.out.println("shipWithinDays OK");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

bool canShip(const std::vector<int>& weights, int days, long long capacity) {
    long long load = 0;
    int needed = 1;
    for (int w : weights) {
        if (load + w > capacity) { ++needed; load = 0; }
        load += w;
    }
    return needed <= days;
}

long long shipWithinDays(const std::vector<int>& weights, int days) {
    long long lo = 0, hi = 0;
    for (int w : weights) { lo = std::max<long long>(lo, w); hi += w; }
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canShip(weights, days, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

int main() {
    assert(shipWithinDays({1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, 5) == 15);
    assert(shipWithinDays({3, 2, 2, 4, 1, 4}, 3) == 6);
    assert(shipWithinDays({1, 2, 3, 1, 1}, 4) == 3);
    assert(shipWithinDays({7}, 1) == 7);
    std::cout << "shipWithinDays OK\n";
}
import assert from "node:assert/strict";

function shipWithinDays(weights: number[], days: number): number {
  const canShip = (capacity: number): boolean => {
    let load = 0, needed = 1;
    for (const w of weights) {
      if (load + w > capacity) { needed++; load = 0; }
      load += w;
    }
    return needed <= days;
  };
  let lo = Math.max(...weights);
  let hi = weights.reduce((s, w) => s + w, 0);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canShip(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

assert.equal(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5), 15);
assert.equal(shipWithinDays([3, 2, 2, 4, 1, 4], 3), 6);
assert.equal(shipWithinDays([1, 2, 3, 1, 1], 4), 3);
assert.equal(shipWithinDays([7], 1), 7);
console.log("shipWithinDays OK");

Binary Search on Answer

This pattern appears constantly in interviews and competitive programming. The framework:

  1. Define a predicate function condition(x) -> bool
  2. Find the boundary where the predicate flips from False to True (or vice versa)
  3. Set lo and hi to the valid range
  4. Binary search for the boundary

If condition(mid) is True and you want the minimum valid value: hi = mid If condition(mid) is False and you want the minimum valid value: lo = mid + 1

Trace for weights = [1, 2, …, 10], days = 5 (computed by script; "days needed" is what the greedy can_ship counts):

IterationlohimidDays needed at midcan_ship?Update
11055322yeshi = 32
21032213yeshi = 21
31021155yeshi = 15
41015126nolo = 13
51315146nolo = 15
end1515return 15

Why the greedy check and the search are both correct. The greedy can_ship fills each day as much as possible; any valid schedule can be transformed into the greedy one without using more days (moving a package earlier never hurts), so greedy computes the minimum number of days for a given capacity. That minimum is non-increasing in capacity, so can_ship is monotone: false below the answer, true from the answer on. The loop keeps the invariant "the answer is in [lo, hi]" — hi is always feasible, everything below lo is infeasible — and stops when they meet. Note the loop shape: while lo < hi with hi = mid (never mid - 1, since mid might be the answer) and lo = mid + 1. Mixing this shape with the lo <= hi shape of the standard search is the classic source of infinite loops.

Sorting in Practice

Language Built-in Sorts

LanguageAlgorithmStable?
Python list.sort()TimSort (merge + insertion)Yes
JavaScript Array.sort()TimSort (V8), varies by engineDepends on engine
Java Arrays.sort() (primitives)Dual-pivot quicksortNo
Java Arrays.sort() (objects)TimSortYes
C++ std::sort()Introsort (quick + heap + insertion)No
C++ std::stable_sort()Merge sortYes

Correction

Array.prototype.sort is required to be stable since ECMAScript 2019, and all major engines comply (V8 has used Timsort since V8 7.0 in 2018). "Depends on engine" is only true of pre-2019 engines. Two more details worth knowing: Python's Timsort switched its merge-ordering policy to Powersort in CPython 3.11, and Java's primitive dual-pivot quicksort (Yaroslavskiy, JDK 7) gained further fallbacks in later JDKs, so "dual-pivot quicksort" describes the core, not the whole routine. Sorting in the Real World has the full table, including Go (pdqsort since 1.19) and Rust.

Custom Comparators

from functools import cmp_to_key

# Sort by multiple criteria
users = [("Alice", 30), ("Bob", 25), ("Charlie", 30)]
users.sort(key=lambda u: (u[1], u[0]))  # (age, name) tuple comparison

# Custom comparator for complex ordering
def compare_versions(v1: str, v2: str) -> int:
    parts1 = list(map(int, v1.split(".")))
    parts2 = list(map(int, v2.split(".")))
    for p1, p2 in zip(parts1, parts2):
        if p1 != p2:
            return p1 - p2
    return len(parts1) - len(parts2)

versions = ["1.2.3", "1.0.1", "1.2.1"]
versions.sort(key=cmp_to_key(compare_versions))


# --- self-check (same data in all four languages) ---
assert users == [("Bob", 25), ("Alice", 30), ("Charlie", 30)]
assert versions == ["1.0.1", "1.2.1", "1.2.3"]
assert sorted(["1.10", "1.9", "1.9.1"], key=cmp_to_key(compare_versions)) == ["1.9", "1.9.1", "1.10"]
print("comparators OK")
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Comparators {
    record User(String name, int age) {}

    static int compareVersions(String v1, String v2) {
        String[] a = v1.split("\\."), b = v2.split("\\.");
        for (int i = 0; i < Math.min(a.length, b.length); i++) {
            int c = Integer.compare(Integer.parseInt(a[i]), Integer.parseInt(b[i]));
            if (c != 0) return c;
        }
        return Integer.compare(a.length, b.length);
    }

    static void check(boolean ok, String m) { if (!ok) throw new AssertionError(m); }

    public static void main(String[] args) {
        List<User> users = new ArrayList<>(List.of(new User("Alice", 30), new User("Bob", 25), new User("Charlie", 30)));
        users.sort(Comparator.comparingInt(User::age).thenComparing(User::name));   // age, then name
        check(users.stream().map(User::name).toList().equals(List.of("Bob", "Alice", "Charlie")), "users");

        List<String> versions = new ArrayList<>(List.of("1.2.3", "1.0.1", "1.2.1"));
        versions.sort(Comparators::compareVersions);
        check(versions.equals(List.of("1.0.1", "1.2.1", "1.2.3")), "versions");

        List<String> v2 = new ArrayList<>(List.of("1.10", "1.9", "1.9.1"));
        v2.sort(Comparators::compareVersions);
        check(v2.equals(List.of("1.9", "1.9.1", "1.10")), "numeric parts");
        System.out.println("comparators OK");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include <tuple>
#include <vector>

struct User { std::string name; int age; };

std::vector<int> parts(const std::string& v) {
    std::vector<int> out;
    std::stringstream ss(v);
    std::string tok;
    while (std::getline(ss, tok, '.')) out.push_back(std::stoi(tok));
    return out;
}

int compareVersions(const std::string& v1, const std::string& v2) {
    std::vector<int> a = parts(v1), b = parts(v2);
    for (std::size_t i = 0; i < std::min(a.size(), b.size()); ++i)
        if (a[i] != b[i]) return a[i] < b[i] ? -1 : 1;
    return a.size() == b.size() ? 0 : (a.size() < b.size() ? -1 : 1);
}

int main() {
    std::vector<User> users = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 30}};
    std::sort(users.begin(), users.end(), [](const User& x, const User& y) {
        return std::tie(x.age, x.name) < std::tie(y.age, y.name);    // age, then name
    });
    assert(users[0].name == "Bob" && users[1].name == "Alice" && users[2].name == "Charlie");

    std::vector<std::string> versions = {"1.2.3", "1.0.1", "1.2.1"};
    std::sort(versions.begin(), versions.end(),
              [](const std::string& x, const std::string& y) { return compareVersions(x, y) < 0; });
    assert((versions == std::vector<std::string>{"1.0.1", "1.2.1", "1.2.3"}));

    std::vector<std::string> v2 = {"1.10", "1.9", "1.9.1"};
    std::sort(v2.begin(), v2.end(),
              [](const std::string& x, const std::string& y) { return compareVersions(x, y) < 0; });
    assert((v2 == std::vector<std::string>{"1.9", "1.9.1", "1.10"}));
    std::cout << "comparators OK\n";
}
import assert from "node:assert/strict";

// Sort objects by multiple keys
const users = [
  { name: "Alice", age: 30 },
  { name: "Bob", age: 25 },
  { name: "Charlie", age: 30 },
];

users.sort((a, b) => {
  if (a.age !== b.age) return a.age - b.age; // ascending age
  return a.name.localeCompare(b.name);         // then alphabetical
});

function compareVersions(v1: string, v2: string): number {
  const a = v1.split(".").map(Number), b = v2.split(".").map(Number);
  for (let i = 0; i < Math.min(a.length, b.length); i++) {
    if (a[i] !== b[i]) return a[i] - b[i];
  }
  return a.length - b.length;
}

// --- self-check ---
assert.deepEqual(users.map((u) => u.name), ["Bob", "Alice", "Charlie"]);
assert.deepEqual(["1.2.3", "1.0.1", "1.2.1"].sort(compareVersions), ["1.0.1", "1.2.1", "1.2.3"]);
assert.deepEqual(["1.10", "1.9", "1.9.1"].sort(compareVersions), ["1.9", "1.9.1", "1.10"]);
console.log("comparators OK");

A comparator must define a strict weak ordering: irreflexive, transitive, and with "neither is less" being an equivalence. Violating it is not merely a wrong order: C++'s std::sort may read out of bounds, and Java's TimSort throws IllegalArgumentException: Comparison method violates its general contract!. The usual offenders are comparators that mix < and <=, that compare floating-point values containing NaN, or that return a - b on 32-bit integers, which overflows (Integer.MIN_VALUE - 1 is positive). Prefer key functions (key= in Python, Comparator.comparing in Java, std::tie in C++), which cannot be inconsistent.

The Lower Bound

Any comparison-based sorting algorithm must make at least comparisons in the worst case. The proof uses a decision tree argument: there are possible orderings, and each comparison can only halve the remaining possibilities.

This is why counting sort and radix sort are faster — they bypass comparisons by using the structure of the data itself.

The bound is concrete, not just asymptotic. For , , so every comparison sort needs at least 22 comparisons on some input of ten elements. For , , while — merge sort's worst case is within about 17% of optimal. The same argument gives for searching a sorted array (there are possible answers), which is why binary search is optimal among comparison-based searches; hashing escapes that bound the same way counting sort escapes the sorting bound, by not comparing. The Non-Comparison Sorts lesson proves with Stirling's approximation and states the average-case version.

Real-world uses

  • Standard libraries. Python's list.sort and sorted are Timsort with the Powersort merge policy; Java sorts objects with Timsort and primitives with dual-pivot quicksort; V8 (Chrome, Node.js) uses Timsort; C++ std::sort is introsort in libstdc++ and MSVC; Go's sort and slices packages use pattern-defeating quicksort since Go 1.19; the Linux kernel's lib/sort.c is heap sort, chosen because it needs no extra memory and has no quadratic case. Details in Sorting in the Real World.
  • Databases. ORDER BY on data larger than the sort memory becomes an external merge sort: sort memory-sized runs, write them to disk, then -way merge them with a heap (PostgreSQL's EXPLAIN ANALYZE reports Sort Method: external merge). Sort-merge joins sort both inputs on the join key and walk them with two pointers. B-tree pages are searched with binary search over their sorted keys, and LSM-tree compaction is a multi-way merge of sorted runs. See Indexing Deep Dive, Storage Engines and Query Planning & Optimization.
  • Distributed systems. Consistent hashing keeps node positions on a sorted ring and finds a key's owner with a binary search for the first position at or after the key's hash (Consistent Hashing). MapReduce-style jobs sort by key during the shuffle; the classic TeraSort benchmark is literally "sort a terabyte".
  • Version control and debugging. git bisect is binary search over commit history: given a good and a bad commit, it finds the first bad one in tests. The same idea finds the first failing input size, the build flag that broke performance, or the config change that caused an incident.
  • Operating systems and networking. Routing tables find the longest matching prefix with tries and sorted tables; the kernel's bsearch looks up sorted exception tables and symbol tables; CPU schedulers keep run queues ordered (CPU Scheduling).
  • Search engines. Posting lists are sorted document-ID arrays; intersecting the lists for a multi-word query is a merge, or galloping (exponential) search when one list is much shorter (Search Engineering).

Pitfalls & edge cases

  1. Integer overflow in mid. (lo + hi) / 2 overflows a 32-bit int once lo + hi > 2^31 - 1. This bug lived in the JDK's Arrays.binarySearch for about nine years before Joshua Bloch's 2006 write-up. Use lo + (hi - lo) / 2 or (lo + hi) >>> 1 in Java.
  2. Infinite loops from mixed loop shapes. With while lo < hi, an update lo = mid loops forever when hi = lo + 1 (because mid == lo). Either use lo = mid + 1 / hi = mid with a floor midpoint, or lo = mid / hi = mid - 1 with a ceiling midpoint. Pick one template per variant and never mix.
  3. Binary search on unsorted or wrongly sorted data. It returns a plausible wrong answer rather than an error. Sorting with a different comparator than the one you search with is the subtle version.
  4. JavaScript's default sort is lexicographic. [10, 9, 1].sort() returns [1, 10, 9] because it compares strings. Always pass (a, b) => a - b for numbers.
  5. Comparators that are not strict weak orderings. a - b overflow on extreme integers, <= instead of < in C++ (undefined behaviour), random comparators used to "shuffle", NaN in floating-point keys. Use key functions where the language offers them.
  6. Assuming a sort is stable. std::sort, Java's primitive Arrays.sort, heap sort and quicksort are not. If you rely on equal elements keeping their order, use std::stable_sort, sort objects in Java, or add the original index as a tiebreaker.
  7. list.sort() returns None. In Python, x = x.sort() sets x to None; use sorted(x) for a new list. Similarly Arrays.sort returns void in Java, and JavaScript's sort sorts in place and returns the same array (use toSorted() for a copy).
  8. Counting sort with negatives or huge ranges. The version above crashes (Python indexes from the end of the list for negative indices — silently wrong) or allocates gigabytes when one value is . Offset by the minimum, and fall back to a comparison sort when .
  9. Radix sort and signed integers. Unsigned byte digits put negative numbers after positives. Flip the sign bit or offset first.
  10. Quicksort recursion depth. A naive quicksort on 1,000,000 already-sorted elements with a last-element pivot nests a million calls and overflows the stack before it finishes being slow. Randomise, recurse on the smaller side, or use introsort.
  11. Rotated search with duplicates. nums[lo] <= nums[mid] no longer proves the left half is sorted when nums[lo] == nums[mid] == nums[hi]; shrink both ends by one in that case and accept worst case (LeetCode 81 and 154).
  12. Wrong bounds on binary search on the answer. Starting lo = 0 for ship capacity wastes iterations and can make the predicate meaningless (a capacity below the heaviest package can never ship). Set lo to the smallest value that could possibly work and hi to one that surely works, and make sure hi really is feasible.
  13. Sorting when you only need part of the order. A full sort to get the top 10 of a million items, or the median, is the most common performance mistake in this module. Use a heap or quickselect.

Practice Problems

ProblemTechniqueDifficulty
Merge Sorted ArrayMerge from backEasy
Sort Colors (Dutch National Flag)Three-way partitionMedium
Kth Largest ElementQuick select / heapMedium
Search in Rotated Sorted ArrayModified binary searchMedium
Find Peak ElementBinary searchMedium
Search a 2D MatrixBinary searchMedium
Median of Two Sorted ArraysBinary searchHard
Count of Smaller Numbers After SelfMerge sort + countHard
Find Minimum in Rotated Sorted ArrayBinary searchMedium
Capacity To Ship PackagesBinary search on answerMedium

Practice ladder

Fifteen problems, easiest first; each builds on the one before. Descriptions are in our own words — follow the link for the official statement.

1. Binary Search (LeetCode 704) — Return the index of a target in a sorted array of distinct integers, or -1. Teaches the closed-interval template and its loop condition.

Hint

lo = 0, hi = n - 1, while lo <= hi. Write it from memory, then test it on an empty array, a one-element array, and targets smaller than the first and larger than the last element.

2. Merge Sorted Array (LeetCode 88) — Merge a second sorted array into the first, which has exactly enough trailing free space, in place. Teaches the merge step and why filling from the back avoids overwriting unread values.

Hint

Three pointers: the last real element of each array and the last slot of the first. Repeatedly place the larger of the two candidates at the back.

Solution
def merge_in_place(nums1: list[int], m: int, nums2: list[int], n: int) -> None:
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:                       # once nums2 is used up, nums1's prefix is in place
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1


a = [1, 2, 3, 0, 0, 0]
merge_in_place(a, 3, [2, 5, 6], 3)
assert a == [1, 2, 2, 3, 5, 6]
b = [0]
merge_in_place(b, 0, [1], 1)
assert b == [1]
print("ok")

time, extra space. The write index k never overtakes the read index i, because k - i = j + 1 > 0 while nums2 still has elements.

3. Search Insert Position (LeetCode 35) — Return the index of the target, or where it would be inserted. Teaches that a failed binary search ends with lo at the insertion point (the trace above).

Hint

The standard search, but return lo instead of -1. Equivalently, the first index with nums[i] >= target (bisect_left).

4. Sort Colors (LeetCode 75) — Sort an array of 0s, 1s and 2s in one pass and constant space. Teaches the Dutch national flag three-way partition, the same partition that makes quicksort robust to duplicates.

Hint

Three regions: [0, lo) is 0, [lo, mid) is 1, (hi, n-1] is 2, [mid, hi] unknown. Look at nums[mid] and swap it into its region. Do not advance mid after swapping with hi.

Solution
def sort_colors(nums: list[int]) -> None:
    lo, mid, hi = 0, 0, len(nums) - 1
    while mid <= hi:
        if nums[mid] == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1                     # the swapped-in value is unexamined: keep mid


c = [2, 0, 2, 1, 1, 0]
sort_colors(c)
assert c == [0, 0, 1, 1, 2, 2]
d = [2, 0, 1]
sort_colors(d)
assert d == [0, 1, 2]
print("ok")

time, one pass, space. Each iteration shrinks the unknown region [mid, hi] by one.

5. Find First and Last Position of Element in Sorted Array (LeetCode 34) — Return the first and last index of a target in . Teaches boundary searches.

Hint

find_first and find_last from this page, or bisect_left(target) and bisect_left(target + 1) - 1.

6. Merge Intervals (LeetCode 56) — Merge all overlapping intervals. Teaches sorting as preprocessing: after sorting by start, overlaps are only ever between neighbours.

Hint

Sort by start. Keep the last merged interval; if the next start is at most its end, extend the end to the maximum of the two ends, otherwise start a new interval. More in Intervals.

7. Kth Largest Element in an Array (LeetCode 215) — The -th largest without fully sorting. Teaches quickselect versus a size- heap.

Hint

Quickselect for index n - k with a random pivot and a three-way partition (the test data has many duplicates), or a min-heap of size k. Full treatment in Quickselect & Order Statistics.

8. Find Minimum in Rotated Sorted Array (LeetCode 153) — Find the minimum of a rotated sorted array of distinct values. Teaches binary search on a predicate that is not "equals target".

Hint

Compare nums[mid] with nums[hi]: if greater, the minimum is strictly right of mid (lo = mid + 1); otherwise it is at mid or left of it (hi = mid). Loop while lo < hi.

9. Search in Rotated Sorted Array (LeetCode 33) — Find a target in a rotated sorted array in . Teaches "one half is always sorted".

Hint

search_rotated above. Alternatively: find the rotation point with problem 8, then binary search the correct run.

10. Find Peak Element (LeetCode 162) — Return any index whose value exceeds both neighbours (out-of-range neighbours count as ). Teaches that binary search needs only a local signal, not global sortedness.

Hint

If nums[mid] < nums[mid + 1], a peak exists to the right (walk uphill and you must eventually stop); otherwise one exists at mid or to the left.

11. Search a 2D Matrix (LeetCode 74) — Each row is sorted and each row starts after the previous row ends. Teaches index mapping: the matrix is one sorted array of length .

Hint

Binary search over 0 … m*n - 1 and read element i as matrix[i // n][i % n].

12. Koko Eating Bananas (LeetCode 875) — Find the minimum eating speed that finishes all piles within h hours. Teaches binary search on the answer with a ceiling-division predicate.

Hint

Hours needed at speed s is the sum of ceil(p / s); it is non-increasing in s. Search s in [1, max(piles)].

Solution
def min_eating_speed(piles: list[int], h: int) -> int:
    def hours(speed: int) -> int:
        return sum((p + speed - 1) // speed for p in piles)   # integer ceil

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid
        else:
            lo = mid + 1
    return lo


assert min_eating_speed([3, 6, 7, 11], 8) == 4
assert min_eating_speed([30, 11, 23, 4, 20], 5) == 30
assert min_eating_speed([30, 11, 23, 4, 20], 6) == 23
print("ok")

where . hi = max(piles) is always feasible because then every pile takes one hour and the problem guarantees h >= len(piles).

13. Capacity To Ship Packages Within D Days (LeetCode 1011) — The worked example on this page. Teaches choosing tight bounds (max and sum) and proving the greedy predicate monotone.

Hint

ship_within_days above. Then try Split Array Largest Sum (LeetCode 410), which is the same problem in disguise.

14. Largest Number (LeetCode 179) — Arrange non-negative integers to form the largest possible concatenated number. Teaches designing a comparator and checking that it is a valid ordering.

Hint

Put a before b if the string a + b is larger than b + a. This relation is transitive (it is equivalent to comparing with ), so sorting with it is legal. Watch out for an all-zero input.

Solution
from functools import cmp_to_key


def largest_number(nums: list[int]) -> str:
    strs = [str(x) for x in nums]

    def cmp(a: str, b: str) -> int:
        if a + b > b + a:
            return -1           # a goes first
        if a + b < b + a:
            return 1
        return 0

    strs.sort(key=cmp_to_key(cmp))
    result = "".join(strs)
    return "0" if result[0] == "0" else result


assert largest_number([10, 2]) == "210"
assert largest_number([3, 30, 34, 5, 9]) == "9534330"
assert largest_number([0, 0]) == "0"
print("ok")

comparisons, each for numbers of up to digits.

15. Count of Smaller Numbers After Self (LeetCode 315) — For each element, count the smaller elements to its right. Teaches counting inversions inside merge sort while tracking original indices.

Hint

Merge sort an array of indices by value. When an element from the left half is emitted during a merge, every element already emitted from the right half is smaller and was originally to its right: add that count to the element's answer.

Solution
def count_smaller(nums: list[int]) -> list[int]:
    counts = [0] * len(nums)

    def sort(idx: list[int]) -> list[int]:
        if len(idx) <= 1:
            return idx
        mid = len(idx) // 2
        left, right = sort(idx[:mid]), sort(idx[mid:])
        merged, j = [], 0
        for i in left:
            while j < len(right) and nums[right[j]] < nums[i]:
                merged.append(right[j])
                j += 1
            counts[i] += j              # right elements already emitted are smaller
            merged.append(i)
        merged.extend(right[j:])
        return merged

    sort(list(range(len(nums))))
    return counts


assert count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0]
assert count_smaller([-1]) == [0]
assert count_smaller([-1, -1]) == [0, 0]
print("ok")

time, space. The strict < matters: equal values are not "smaller". The Merge Sort lesson covers the general inversion-counting technique, and a Fenwick tree over compressed values solves the same problem in Module 3.

Common mistakes & interview follow-ups

What interviewers ask after your first answer, and what they want to hear:

  • "Which sorting algorithm does your language use, and is it stable?" Know your row of the built-in table (with the correction above). Mention that the object sorts are stable Timsort in Python, Java and JavaScript, and that C++ std::sort is unstable introsort — use std::stable_sort when order of equals matters.
  • "Why is quicksort usually faster than merge sort when it does more comparisons?" It works in place with sequential access and a tight inner loop, needs no auxiliary array, and its data stays in cache. Merge sort moves every element at every level. The 39% extra comparisons cost less than the extra memory traffic.
  • "How would you sort 100 GB of data on a machine with 8 GB of RAM?" External merge sort: read about 8 GB at a time, sort it, write it out as a sorted run (about 13 runs), then merge all runs at once with a min-heap of their current heads, using buffered sequential I/O. Two passes over the data in total.
  • "How would you sort a billion 32-bit integers?" Radix sort with 8- or 16-bit digits (four or two passes), or counting sort if the range is small. Mention memory: an auxiliary array of the same size is needed.
  • "The array is nearly sorted: every element is at most positions from its final place." Insertion sort is ; a min-heap of size sliding along the array is .
  • "Your binary search works for distinct values. What if there are duplicates?" Switch to a boundary search: first index with nums[i] >= target and first index with nums[i] > target. Their difference is the count.
  • "What if the array is too large to know its length (an infinite or streamed sorted sequence)?" Exponential search: probe indices 1, 2, 4, 8, … until you pass the target, then binary search the last interval — where is the target's position (Other Searches).
  • "Can you binary search on a linked list?" Not in : reaching the middle costs . Use a skip list or a balanced BST (Module 3) if you need ordered search on a dynamic set.
  • "How would you sort a linked list?" Merge sort: splitting with slow/fast pointers and merging by relinking needs no random access and extra space for the merge (Linked Lists).
  • "Prove your binary search terminates." The interval [lo, hi] shrinks by at least one element every iteration (because mid itself is excluded, or because lo < hi guarantees mid < hi), so the loop runs at most times; halving gives the bound.
  • "What is the lower bound for sorting, and how does radix sort beat it?" comparisons, from the decision-tree argument. Radix sort is not a comparison sort: it inspects digits, so the decision-tree model does not apply.

Further Reading

  • Heaps & Priority Queues — heap sort and partial sorting
  • Arrays & Strings — two pointers on sorted arrays
  • Dynamic Programming — LIS uses binary search optimization
  • Database Query Planning — how databases choose sort algorithms
  • Searching & Sorting module index and every deep lesson listed in How this module is organised
  • Benchmarks — how to measure sorts fairly, used in the capstone
  • CLRS, Introduction to Algorithms, 3rd ed., Chapter 2 (insertion sort, merge sort), Chapter 6 (heapsort), Chapter 7 (quicksort), Chapter 8 (lower bound, counting, radix and bucket sort), Chapter 9 (selection)
  • R. Sedgewick and K. Wayne, Algorithms, 4th ed., Chapter 2 (Sorting) and §3.1 (binary search in symbol tables)
  • S. Skiena, The Algorithm Design Manual, 3rd ed., Chapter 4 (Sorting and Searching) — strong on applications and war stories
  • D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching — the definitive reference
  • J. Bentley, Programming Pearls, 2nd ed., Columns 4 and 5 — writing a correct binary search, and why most programmers cannot
  • J. Bloch, "Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken", Google Research Blog, 2006
  • T. Peters, listsort.txt (CPython source) — the design notes for Timsort
  • cp-algorithms: binary search

Module 2 navigation. This is the first lesson of the module. Previous: Capstone: Build an LRU Cache & Benchmark It (end of Module 1). Next: Elementary Sorts & Stability. Module overview: Searching & Sorting. Course home: DSA: Zero to Mastery.

Try It Yourself

Problem 1: Sort the array [5, 3, 8, 4, 2] using merge sort. Show the divide and merge steps.

Solution

Divide:

  • [5, 3, 8, 4, 2] → [5, 3] and [8, 4, 2]
  • [5, 3] → [5] and [3]
  • [8, 4, 2] → [8] and [4, 2] → [4] and [2]

Merge:

  • Merge [5] and [3] → [3, 5]
  • Merge [4] and [2] → [2, 4]
  • Merge [8] and [2, 4] → [2, 4, 8]
  • Merge [3, 5] and [2, 4, 8] → [2, 3, 4, 5, 8]

Problem 2: Use binary search to find target 7 in [1, 3, 5, 7, 9, 11, 13].

Solution
  • lo=0, hi=6, mid=3. nums[3]=7 == target. Answer: Found at index 3 in 1 step.

Problem 3: Search for target 5 in the rotated sorted array [4, 5, 6, 7, 0, 1, 2].

Solution

Modified binary search:

  • lo=0, hi=6, mid=3. nums[3]=7 != 5.
  • Left half [4,5,6,7] is sorted (nums[0]=4 <= nums[3]=7). Is 4 <= 5 < 7? Yes → search left: hi=2.
  • lo=0, hi=2, mid=1. nums[1]=5 == target. Answer: Found at index 1.

Problem 4: Find the Kth largest element (K=2) in [3, 2, 1, 5, 6, 4] without fully sorting.

Solution

Use a min-heap of size K=2:

  • Process 3: heap=[3]
  • Process 2: heap=[2,3]
  • Process 1: 1 < heap[0]=2, skip (or push and pop)
  • Process 5: push, pop min → heap=[3,5]
  • Process 6: push, pop min → heap=[5,6]
  • Process 4: 4 < heap[0]=5, skip Answer: heap[0] = 5 (2nd largest element)

Problem 5: Given weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and D=5 days, find the minimum ship capacity to ship all packages within D days using binary search on the answer.

Solution
  • lo = max(weights) = 10, hi = sum(weights) = 55
  • Binary search: mid=32 → can ship in 2 days (yes), hi=32
  • mid=21 → can ship in 3 days (yes), hi=21
  • mid=15 → can ship in 5 days (yes), hi=15
  • mid=12 → need 6 days > 5 (no), lo=13
  • mid=14 → can ship in 5 days (yes), hi=14
  • mid=13 → need 6 days (no), lo=14 Answer: Minimum capacity = 15

Correction: the last two steps above are wrong (and inconsistent with the stated answer). At capacity 14 the greedy loads are [1–4], [5, 6], [7], [8], [9], [10] — 6 days, so 14 is infeasible. The real search, checked by script, is: mid=32 (2 days, yes, hi=32) → mid=21 (3 days, yes, hi=21) → mid=15 (5 days, yes, hi=15) → mid=12 (6 days, no, lo=13) → mid=14 (6 days, no, lo=15) → lo = hi = 15. The answer 15 is correct; see the trace table in Binary Search on Answer.

Problem 6: Partition [7, 2, 9, 4, 3, 8, 6] with the Lomuto scheme using the last element as pivot. Where does the pivot end up, and what is the array afterwards?

Solution

Pivot 6. Elements are 2, 4, 3, which are swapped to the front in that order; the pivot is then swapped into index 3. Result: [2, 4, 3, 6, 9, 8, 7], pivot at index 3 (see the partition trace above).

Problem 7: How many comparisons does any comparison sort need, in the worst case, to sort 5 elements? Does merge sort achieve it?

Solution

. Top-down merge sort splits 5 into 2 + 3 and uses up to comparisons in the worst case, so it does not reach the bound; a specially designed sorting network or the Ford–Johnson merge-insertion algorithm sorts 5 elements in 7.

Quick Quiz

1. What is the best sorting algorithm for nearly-sorted data?

  • a) Quick sort
  • b) Merge sort
  • c) Insertion sort
  • d) Heap sort
Answer

c) Insertion sort — Insertion sort has best-case performance when data is nearly sorted, as elements only need to shift a few positions. All comparison-based sorts do unnecessary work on nearly-sorted input.

2. Why does quicksort have worst-case time complexity?

  • a) The merge step is inefficient
  • b) The pivot selection consistently picks the minimum or maximum element, creating unbalanced partitions
  • c) It uses too much memory
  • d) It cannot handle duplicate elements
Answer

b) The pivot selection consistently picks the minimum or maximum element, creating unbalanced partitions — When the pivot is always the smallest or largest element (e.g., sorted input with first/last pivot), one partition has elements and the other has 0, giving .

3. What is the theoretical lower bound for comparison-based sorting?

  • a)
  • b)
  • c)
  • d)
Answer

b) — The decision tree argument shows that distinguishing between possible orderings requires at least comparisons.

Note: a lower bound is properly written with : every comparison sort needs comparisons in the worst case. is an upper-bound notation.

4. In binary search, why should you compute mid as lo + (hi - lo) / 2 instead of (lo + hi) / 2?

  • a) It is faster to compute
  • b) It prevents integer overflow when lo + hi exceeds the maximum integer value
  • c) It gives a different result
  • d) It works better with floating-point numbers
Answer

b) It prevents integer overflow when lo + hi exceeds the maximum integer value — In languages with fixed-size integers (C, C++, Java), lo + hi can overflow. Subtracting first avoids this. In Python and JavaScript this is not strictly necessary, but it is a good habit.

5. When is counting sort preferred over comparison-based sorts?

  • a) When the data is floating-point
  • b) When the data consists of integers in a known, small range
  • c) When stability is not required
  • d) When memory is extremely limited
Answer

b) When the data consists of integers in a known, small range — Counting sort runs in where is the range of values. When , it is linear, beating the lower bound of comparison sorts.

6. You sort a list of orders by date, then sort the result by customer name. When does each customer's orders stay in date order?

Answer

Exactly when the second sort is stable. A stable sort keeps equal keys (same customer) in their existing relative order, which is date order from the first sort. With an unstable sort such as std::sort or heap sort, the date order within a customer can be scrambled. Alternatively, sort once by the composite key (customer, date).

7. A binary search uses while lo < hi with mid = (lo + hi) // 2 and the updates lo = mid / hi = mid - 1. What goes wrong?

Answer

When hi = lo + 1, mid = lo, and if the branch taken is lo = mid, nothing changes: an infinite loop. With lo = mid the midpoint must round up: mid = (lo + hi + 1) // 2. Floor midpoints pair with lo = mid + 1 / hi = mid.