Intro Sort

Intro sort, short for introspective sort, is the hybrid sorting algorithm published by David Musser in 1997 (Musser, Software: Practice and Experience 27.8) that powers C++‘s std::sort in essentially every modern standard-library implementation (libstdc++, libc++, MSVC STL). It begins as ordinary Quicksort and introspects on its own recursion depth as it runs: if the depth exceeds a threshold of 2 ⌊log₂ n⌋, signaling that quicksort’s pivot selection has wandered into the pathological Θ(n²) regime, the algorithm switches the offending subproblem to Heap Sort mid-recursion. Small subarrays (typically n ≤ 16, exact constant varying by implementation) are deferred to Insertion Sort either inline or in a final cleanup pass. The result is an algorithm with quicksort’s average-case speed and constant factor, heap sort’s O(n log n) worst-case guarantee, and insertion sort’s small-array efficiency — a strict Pareto improvement over each component on its own. Intro sort is the closest the comparison-sort community has to a single “right answer” for general-purpose sorting of unstructured data, and is one of the canonical examples in the algorithms literature of how combining well-understood algorithms produces something better than any of them individually.

1. Intuition — Three Specialists Sharing One Job

Imagine you are scheduling three specialists to sort a stack of files:

• The Hare (quicksort) is the fastest on most jobs because she works in cache-friendly forward sweeps and finishes typical inputs quickly. But on adversarially-arranged stacks she can get stuck spending quadratic time on imbalanced splits.
• The Tortoise (heap sort) is steady — she always finishes in O(n log n) no matter how bad the input is — but her constant factor is larger and she is cache-unfriendly because the heap-index arithmetic causes random-feeling jumps across the array.
• The Apprentice (insertion sort) is unbeatable when the stack is small or already nearly sorted, because she just slides the next item leftward into place, skipping work whenever possible. On a large random stack, she is too slow.

Intro sort’s policy is: let the Hare start the job. Watch her over her shoulder. The moment her recursion depth crosses 2 ⌊log₂ n⌋ — proof that her pivots have produced badly imbalanced partitions and she is at risk of quadratic time — interrupt her and hand the offending pile to the Tortoise. For any pile that has shrunk below ~16 elements, hand it to the Apprentice instead. The “introspection” is the depth-watching. There is no probabilistic argument, no sampling, no try-and-retry: the algorithm makes a deterministic decision based on how deep it has recursed so far.

The non-obvious insight is why the depth threshold is 2 ⌊log₂ n⌋ specifically. A perfectly balanced quicksort recurses to depth ⌈log₂ n⌉. If pivots produce splits of roughly 1:9 (rather than 1:1), the recursion depth roughly doubles. Musser chose 2 ⌊log₂ n⌋ as the empirical breakpoint at which “we are deep enough that quicksort is provably wasting work, but not so deep that we have already paid catastrophic cost.” Switching at this depth caps the work spent on the bad subproblem at O(m log m) where m is its size, preserving the overall O(n log n) worst-case bound. The factor of 2 is conventional but not sacred — some implementations use 1.5 log₂ n or other small multiples; the bound is robust across reasonable choices.

2. Tiny Worked Example

Let n = 8. The depth limit is 2 ⌊log₂ 8⌋ = 2 · 3 = 6.

Suppose we are sorting an adversarial input where the pivot selector keeps choosing the worst possible pivot, so each partition splits as (n − 1, 0) — completely unbalanced. The recursion would normally proceed:

depth 0:  size 8 → partition → (7, 0)         [pivot was max]
depth 1:  size 7 → partition → (6, 0)
depth 2:  size 6 → partition → (5, 0)
depth 3:  size 5 → partition → (4, 0)
depth 4:  size 4 → partition → (3, 0)
depth 5:  size 3 → partition → (2, 0)
depth 6:  size 2 → ⚠️ DEPTH LIMIT HIT

At depth 6 (the depth-limit threshold), the algorithm stops trying to quicksort the size-2 subproblem and either (a) calls Heap Sort on it directly, or (b) more typically, since the subarray is below the small-array threshold (16 elements), defers it to Insertion Sort.

The interesting case is where the subproblem at the depth limit is not tiny. Imagine a different adversarial input that produces 1:7 splits at every recursion: depth 0 partitions size 8 into (7, 1), depth 1 partitions the size-7 subproblem into (6, 1), and so on. By depth 6, we are still working on a subproblem of substantial size (in this small example, perhaps size 2 — but in a larger input, perhaps several hundred). At that point, intro sort abandons further quicksort recursion on the size-m remainder and invokes heap sort on it. Heap sort guarantees O(m log m) time and O(1) space, so the worst-case total cost is bounded by the geometric series Σ_{i} m_i log m_i ≤ O(n log n) because the subproblem sizes form a decreasing sequence summing to at most n.

For a non-adversarial input — e.g., random data — the depth never approaches 2 ⌊log₂ n⌋, the heap-sort branch never fires, and intro sort’s behavior is identical to quicksort’s. This is the design intent: the heap-sort fallback is insurance, not the common-case engine. Empirically, on random data of size 10⁶, the heap-sort branch fires on under 0.001 % of subproblems.

3. Pseudocode

intro_sort(arr):
    n := length(arr)
    depth_limit := 2 * floor(log2(n))
    intro_sort_loop(arr, 0, n - 1, depth_limit)
    insertion_sort(arr)                          # final cleanup pass

intro_sort_loop(arr, lo, hi, depth_limit):
    while hi - lo > THRESHOLD:                   # THRESHOLD ≈ 16
        if depth_limit == 0:
            heap_sort(arr, lo, hi)               # worst-case O((hi-lo) log (hi-lo))
            return
        depth_limit := depth_limit - 1
        pivot_idx := median_of_three(arr, lo, lo + (hi - lo) / 2, hi)
        p := partition(arr, lo, hi, pivot_idx)   # Lomuto: p is the final pivot index
        intro_sort_loop(arr, p + 1, hi, depth_limit)   # recurse on right half
        hi := p - 1                              # tail-call eliminated for left half

The p + 1 … hi / lo … p − 1 split shown here is the Lomuto convention, where partition returns the pivot’s final resting index p and the pivot itself is excluded from both recursive calls. A Hoare-style partition (as used in the Python implementation below and in most production code) instead returns a split point p such that every element in [lo, p − 1] is ≤ every element in [p, hi], with no element guaranteed to be in its final position; the recursion is then on [lo, p − 1] and [p, hi]. The two conventions differ only in the ±1 bookkeeping; both keep the larger side as the looped tail call to bound stack depth at O(log n).

Several deliberate design choices in this pseudocode bear narrating.

• Single final insertion-sort pass. Many implementations defer all small-subarray sorting to a single insertion_sort(arr) call at the very end, rather than calling insertion sort on each small subproblem inline. The trick is that after the quicksort/heapsort partitioning, every element is guaranteed to be within THRESHOLD positions of its final location (since the partitioning has produced subarrays that are already roughly correctly placed). Insertion sort on a “nearly sorted” array runs in O(n · THRESHOLD) total — effectively O(n) — and avoids the overhead of repeated function calls. This trick is in libstdc++; libc++ historically preferred inline insertion-sort calls per subproblem.
• Tail-call elimination on the larger subproblem. Recursing on the smaller subproblem first and looping on the larger keeps the recursion stack at O(log n) worst-case, even on adversarial inputs.
• Median-of-three pivot. Picking the median of arr[lo], arr[mid], arr[hi] substantially reduces (but does not eliminate) the probability of pathological pivot choice. Some implementations use median-of-nine (median of three medians of three) for inputs above a certain size.

4. Python Implementation

Python’s CPython does not actually use intro sort for list.sort — it uses Tim Sort, which is adaptive and stable. But here is a faithful Python reimplementation of intro sort for pedagogical purposes:

import math
 
def intro_sort(arr: list[int]) -> None:
    """In-place introspective sort. Stable: NO. Adaptive: only partly (small-array path)."""
    if len(arr) < 2:
        return
    depth_limit = 2 * math.floor(math.log2(len(arr)))
    _introsort_loop(arr, 0, len(arr) - 1, depth_limit)
    _insertion_sort(arr, 0, len(arr) - 1)        # final cleanup
 
THRESHOLD = 16
 
def _introsort_loop(arr, lo, hi, depth_limit):
    while hi - lo > THRESHOLD:
        if depth_limit == 0:
            _heap_sort_range(arr, lo, hi)
            return
        depth_limit -= 1
        # median-of-three pivot
        mid = (lo + hi) // 2
        a, b, c = arr[lo], arr[mid], arr[hi]
        pivot = sorted([a, b, c])[1]             # the median
        # Hoare-style partition: returns split point p with arr[lo..p-1] <= arr[p..hi]
        p = _partition(arr, lo, hi, pivot)
        _introsort_loop(arr, p, hi, depth_limit) # recurse on right [p, hi]
        hi = p - 1                               # tail-call left [lo, p-1]
 
def _partition(arr, lo, hi, pivot):
    while True:
        while arr[lo] < pivot: lo += 1
        while arr[hi] > pivot: hi -= 1
        if lo >= hi: return lo
        arr[lo], arr[hi] = arr[hi], arr[lo]
        lo += 1; hi -= 1
 
def _insertion_sort(arr, lo, hi):
    for i in range(lo + 1, hi + 1):
        x = arr[i]
        j = i - 1
        while j >= lo and arr[j] > x:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = x
 
def _heap_sort_range(arr, lo, hi):
    """Heap sort on arr[lo..hi] — uses [[Heap Sort]] mechanics on a slice."""
    # Standard build-max-heap on the range, then extract repeatedly.
    n = hi - lo + 1
    def sift_down(i, end):
        while True:
            l = 2 * i + 1; r = 2 * i + 2; largest = i
            if l < end and arr[lo + l] > arr[lo + largest]: largest = l
            if r < end and arr[lo + r] > arr[lo + largest]: largest = r
            if largest == i: return
            arr[lo + i], arr[lo + largest] = arr[lo + largest], arr[lo + i]
            i = largest
    for i in range(n // 2 - 1, -1, -1):
        sift_down(i, n)
    for end in range(n - 1, 0, -1):
        arr[lo + 0], arr[lo + end] = arr[lo + end], arr[lo + 0]
        sift_down(0, end)

This Python implementation is meant to expose the structure clearly, not to be fast (Python’s per-instruction overhead destroys quicksort’s cache-friendliness advantage). The two non-obvious lines: the pivot = sorted([a, b, c])[1] is the median-of-three computation, written for readability; production C++ uses three explicit conditional swaps. The while hi - lo > THRESHOLD is the small-subarray cutoff that defers tiny problems to insertion sort.

5. Complexity Analysis

5.1 Time

Worst case: Θ(n log n). The depth-limit mechanism caps the total work in the quicksort phase. Let the algorithm hit the depth limit on subproblems of sizes m_1, m_2, …, m_k. By construction, Σ m_i ≤ n (the subproblems are disjoint subarrays of the original). Each is then heap-sorted in O(m_i log m_i) ≤ O(m_i log n), contributing O((Σ m_i) log n) = O(n log n) total. The pre-fallback quicksort work is bounded by O(n · depth_limit) = O(n log n): at any fixed recursion depth d, the subarrays live at that depth are disjoint and together span at most n elements, so all the partition scans at depth d cost O(n) combined; and there are at most depth_limit = 2⌊log₂ n⌋ = O(log n) such depths before every still-active subarray is either small enough for insertion sort or kicked to heap sort. Multiplying the per-level O(n) by the O(log n) levels gives O(n log n) for the quicksort phase. Adding the two phases: O(n log n).

Best case: Θ(n log n), same as quicksort — even on already-sorted input intro sort still partitions and recurses. (Unlike Tim Sort, intro sort is not adaptive in the run-detection sense.)

Average case: Θ(n log n) with quicksort’s small constant factor. On random data the depth limit is essentially never reached (the probability of 2 log₂ n consecutive bad pivots with median-of-three selection is astronomically low), so intro sort’s average performance is exactly quicksort’s average performance.

5.2 Space

Auxiliary space: O(log n) for the recursion stack. With tail-call elimination on the larger subproblem at each step, the stack depth is bounded by log₂ n even in the worst case. Heap sort and insertion sort are both O(1) in their auxiliary space, so neither contributes to the total. Intro sort is therefore in-place in the same sense quicksort is: no auxiliary array, only a logarithmic recursion stack.

5.3 Why the Hybrid Beats Each Component

Each component algorithm has a specific weakness that a peer covers:

• Quicksort’s weakness: worst-case Θ(n²) on adversarial pivot sequences. Heap sort covers it: worst-case O(n log n), no matter the input. The depth-limit heuristic detects when quicksort is heading toward its bad case and hands off.
• Quicksort and heap sort’s weakness: both have non-trivial constant overhead per call (function-call cost, partition setup) that is wasteful on tiny subarrays. Insertion sort covers it: for n ≤ 16, insertion sort’s Θ(n²) time is dominated by its tiny constant factor and tight inner loop, beating both alternatives. The threshold mechanism farms out the small problems.
• Heap sort’s weakness in isolation: Θ(n log n) always, but the constant factor is ~2-3× quicksort’s on cache-friendly hardware because of the random-access pattern of heap index arithmetic. Intro sort covers it: by only invoking heap sort on the rare bad-subproblem cases, the higher constant factor only applies to a tiny fraction of total work.
• Insertion sort’s weakness in isolation: Θ(n²) on any non-trivially-sized input. Intro sort covers it: insertion sort is only called on sub-16-element pieces, where n² is ≤ 256 — a single iteration of the outer quicksort loop’s overhead.

The composition is clean because the three algorithms’ strengths and weaknesses are almost perfectly complementary. This is what makes intro sort canonical, not just clever.

6. Production Use

C++ standard-library implementations of std::sort are required by the C++ standard (since C++03; tightened in C++11) to provide O(n log n) worst-case complexity. This requirement essentially mandates intro sort or a similar hybrid; pure quicksort (with its O(n²) worst case) is non-compliant.

• libstdc++ (GCC): uses intro sort with the 2 ⌊log₂ n⌋ depth limit, median-of-three pivot, and a final insertion-sort pass. The small-array cutoff is the constant _S_threshold = 16, defined in bits/stl_algo.h and used by the __sort, __introsort_loop, and __final_insertion_sort functions. Specifically, __introsort_loop stops recursing once a subrange has ≤ _S_threshold elements, leaving the array as a sequence of unsorted-but-roughly-placed runs; the trailing __final_insertion_sort then performs one near-linear insertion-sort sweep over the whole array (per the Wikipedia Introsort article and the libstdc++ source).
• libc++ (LLVM/Clang): historically used intro sort with similar parameters; recent versions (Clang 14+) switched to BlockQuicksort variants and pattern-defeating quicksort (pdqsort) influences. The depth-limit mechanism remains.
• MSVC STL (Microsoft): intro sort with median-of-three.
• Rust’s slice::sort_unstable: uses pdqsort (Pattern-Defeating Quicksort), an intro-sort descendant by Orson Peters that adds branchless partitioning and pattern detection for sorted/reverse-sorted runs. The depth-limit + heap-sort fallback structure is preserved; the partitioning is improved.
• .NET Array.Sort: uses intro sort since .NET 4.5 (replacing the previous quicksort).
• Go: the standard library’s sort package historically used a quicksort/insertion-sort/heapsort hybrid with an insertion-sort cutoff of 12; since Go 1.19 the generic slices.Sort / sort.Sort path uses pdqsort (per the pdqsort paper, Peters 2021, merged into Go 1.19).

The small-array threshold is implementation-specific but the commonly-quoted value is stable, not version-volatile, in the major libraries: libstdc++ pins it at _S_threshold = 16 (verified above), Musser’s original paper used 16 as well, while Go used 12 and Java’s dual-pivot path uses an insertion cutoff of 47 (INSERTION_SORT_THRESHOLD). The right takeaway is that ”≈ 16” is the canonical figure for the introsort lineage specifically; the exact constant differs per library because it is tuned to that library’s partition routine and target hardware, not because it drifts release-to-release.

CPython’s list.sort and Java’s Arrays.sort for object arrays use Tim Sort, not intro sort; Java’s Arrays.sort for primitive arrays uses dual-pivot quicksort (a Vladimir Yaroslavskiy / Jon Bentley / Joshua Bloch variant, introduced in Java 7). The choice between intro sort and Tim sort in standard libraries comes down to whether the language’s design prioritizes worst-case performance on unstructured data (intro sort: C++) or adaptive performance on real-world partially-sorted data with a stability guarantee (Tim sort: Python, Java for objects). Both are correct for their use cases.

7. Stability and Adaptiveness

Stable: No. Intro sort inherits non-stability from both quicksort and heap sort — neither component preserves the relative order of equal elements through partitioning or heapification. C++‘s std::sort is correspondingly not stable; users who need stability call std::stable_sort (which uses an in-place merge sort variant). This is a deliberate language design choice: the unstable version is faster on most inputs, and users who need stability pay for it explicitly.

Adaptive: Partial. Intro sort is adaptive in one specific sense — the small-subarray insertion-sort cleanup runs in essentially O(n) if the array is already nearly sorted after the partitioning passes. But intro sort does not detect already-sorted runs in the input the way Tim Sort does, and it does not short-circuit on sorted inputs (it still partitions and recurses fully). Inputs like [1, 2, 3, …, n] are processed in Θ(n log n) time, not Θ(n). If adaptivity to real-world partially-sorted input matters, Tim Sort is the better choice; if worst-case guarantee on random or adversarial input matters, intro sort wins.

8. Comparison Table

Property	Intro Sort	Pure Quicksort	Merge Sort	Heap Sort	Tim Sort
Worst-case time	O(n log n)	O(n²)	O(n log n)	O(n log n)	O(n log n)
Average-case time	O(n log n), small const	O(n log n), small const	O(n log n), larger const	O(n log n), larger const	O(n log n), small const
Best-case time	O(n log n)	O(n log n)	O(n log n)	O(n log n)	O(n) (sorted input)
Auxiliary space	O(log n)	O(log n) avg, O(n) worst	O(n)	O(1)	O(n)
Stable	No	No	Yes	No	Yes
Adaptive	Partial	No	No	No	Strong
In-place	Yes	Yes	No	Yes	No
Cache behavior	Excellent	Excellent	Good (sequential)	Poor (heap jumps)	Good
Used by	C++ std::sort, .NET Array.Sort, Rust sort_unstable (pdqsort variant)	Naïve textbook	Java Arrays.sort (object), historical Java pre-Tim	Embedded systems, real-time worst-case	Python list.sort, Java Arrays.sort (object, post-Java 7)

The table makes clear why intro sort dominates the C/C++/.NET/Rust family of standard libraries (priority: worst-case bound + cache-friendliness + in-place) while Tim Sort dominates the Python/Java-object family (priority: adaptivity + stability for arbitrary user-defined comparators). Both are correct; they optimize for different deployment environments.

9. Pitfalls

1. Forgetting the depth-limit decrement. A subtle bug in DIY implementations: if the recursive call uses the original depth_limit instead of decrementing it, the depth-limit mechanism never triggers and worst-case input degenerates to pure quicksort’s O(n²). The decrement must happen exactly once per recursive level.
2. Wrong threshold for small-subarray fallback. The choice of 16 (or whatever the implementation uses) is empirical, tied to L1 cache size and instruction-level parallelism on contemporary CPUs. Picking a threshold of 1 or 2 makes the insertion-sort hand-off useless (the function-call overhead exceeds the savings); picking 200+ makes insertion sort dominate and degrades performance. Stick with the standard-library values unless you have benchmarks justifying otherwise.
3. Assuming intro sort is stable. Code that relies on stable sorting (e.g., sort-by-secondary-key) must use std::stable_sort in C++ or Tim Sort-based sorts in Python/Java. Using std::sort and expecting stability is a correctness bug.
4. Calling intro sort on linked lists or other non-random-access structures. Intro sort’s quicksort phase requires O(1) random access to compute median-of-three pivots and partition. On a linked list, Merge Sort is the right choice.
5. Skipping the median-of-three pivot. Picking the first or last element as pivot makes intro sort vulnerable to specific adversarial inputs (sorted, reverse-sorted, “killer adversary” sequences crafted to cause repeated bad splits). The depth-limit mechanism still saves correctness — the algorithm will fall back to heap sort and complete in O(n log n) — but a measurable constant-factor regression results from making the fallback fire on inputs where median-of-three would have avoided it.
6. Conflating intro sort with introselect. Musser’s 1997 paper introduced two introspective algorithms: introsort (for sorting) and introselect (for selection — find the k-th smallest in O(n) worst case). They share the depth-introspection idea but use different fallback algorithms. See Quickselect and Median of Medians for the selection problem.

10. Diagram

flowchart TD
  Start["intro_sort(arr, n)"] --> Init["depth_limit ← 2 ⌊log₂ n⌋"]
  Init --> Loop["intro_sort_loop(lo, hi, depth_limit)"]
  Loop --> SizeCheck{"hi − lo > THRESHOLD<br/>(e.g., 16)?"}
  SizeCheck -- "No (small subarray)" --> Defer["Defer to insertion sort<br/>(or final cleanup pass)"]
  SizeCheck -- "Yes" --> DepthCheck{"depth_limit == 0?"}
  DepthCheck -- "Yes (too deep)" --> Heap["Heap sort this subproblem<br/>O(m log m) worst-case"]
  DepthCheck -- "No" --> Decrement["depth_limit ← depth_limit − 1"]
  Decrement --> Pivot["Median-of-three pivot"]
  Pivot --> Partition["Partition into < pivot, > pivot"]
  Partition --> RecRight["Recurse on right subarray"]
  Partition --> RecLeft["Loop on left subarray<br/>(tail-call elimination)"]
  RecRight --> Loop
  RecLeft --> Loop
  Defer --> End["Return"]
  Heap --> End

What this diagram shows. The control flow of intro sort’s main loop. The algorithm enters the loop with the current subarray bounds and the remaining depth budget. The first decision is the size check: if the subarray is small (≤ 16 elements), it is handed to insertion sort (either inline or as part of a deferred final pass). Otherwise, the depth budget is checked: a budget of zero means quicksort has already recursed too deep and should be aborted in favor of heap sort, which gives a hard O(m log m) guarantee on the size-m subproblem. If both checks pass — the subarray is large enough to warrant quicksort and the depth budget is healthy — the algorithm decrements the budget, picks a median-of-three pivot, partitions, and recurses on both halves (with tail-call elimination on the larger half to keep the stack at O(log n)). The crucial design idea visible in the diagram is that every recursion level pays one unit of depth budget; if the budget runs out, the algorithm self-corrects by switching algorithms rather than trying harder with the same one. This self-correction is why the worst-case time is O(n log n) and not O(n²).

11. Common Interview Problems

Problem	Source	Connection
Implement std::sort from scratch	System-design / language-internals interview	Intro sort is the textbook answer
”Why is std::sort always O(n log n) worst-case?”	C++ language interview	Depth-limit fallback to heap sort
Sort a large array of integers in-place	Generic LeetCode / interview	Intro sort or pdqsort is the production answer
When would you prefer stable_sort over sort?	C++ interview	When equal-element ordering matters; pay the O(n) aux memory
Compare Python’s Tim sort with C++‘s std::sort	Cross-language algorithms discussion	Adaptive + stable vs. worst-case-bounded + in-place

There is no single LeetCode problem that requires intro sort specifically — any sort that meets the asymptotic bound passes. The interview value is in understanding intro sort as the canonical example of algorithm composition: depth-limiting one algorithm with another’s worst-case guarantee, while specializing on small-input regimes with a third.

12. Open Questions

• What is the precise empirical threshold at which median-of-three’s added overhead is worth the reduced fallback rate? Some recent implementations use median-of-nine or “ninther” only when n exceeds a few hundred — verify the threshold in your target standard library.
• How does pdqsort’s branchless partitioning change the relative balance of intro-sort variants on modern superscalar CPUs? Orson Peters’s pdqsort paper (arXiv:2106.05123, published June 2021 — the open-source implementation predates the paper by several years) reports large speedups on patterned inputs while remaining “never significantly slower than regular quicksort”; independent benchmarks vary. The branchless partition idea derives in part from Edelkamp & Weiß’s BlockQuicksort (arXiv:1604.06697).
• Why is 2 ⌊log₂ n⌋ (factor of 2) the conventional depth limit and not 1.5 ⌊log₂ n⌋ or 3 ⌊log₂ n⌋? Musser’s original paper picks 2 as a “reasonable default” without rigorous derivation; later work (e.g., libstdc++) preserves it more from convention than from optimization.

13. See Also

• Quicksort — the average-case engine of intro sort
• Heap Sort — the worst-case fallback half
• Insertion Sort — the small-array specialist
• Tim Sort — Python/Java’s adaptive stable alternative
• Merge Sort — the stable O(n log n) worst-case competitor (used by std::stable_sort)
• Quickselect — the introspective-selection sibling (Musser 1997)
• Median of Medians — the deterministic worst-case O(n) selection algorithm
• Big-O Notation
• SWE Interview Preparation MOC