DSA DSA In Depth
0%
From-Scratch Build

Hybrid IntroSort & Quickselect Order-Statistic Engine

Musser’s hybrid IntroSort (median-of-three 3-way QuickSort + depth-bounded HeapSort fallback + small-subarray InsertionSort) paired with linear-time 3-way Quickselect.

~30 min Intermediate Lessons: Build Lab: Hybrid Adaptive Sort (Run Detection + Insertion + Galloping Merge), Quicksort: Lomuto vs Hoare vs Bentley-McIlroy 3-Way Partitioning, Order Statistics: Randomized Quickselect vs Deterministic BFPRT Median-of-Medians, Production Case Study: Python/V8 TimSort (Galloping & Run Invariants) vs Rust pdqsort, Insertion, Selection & Shellsort: Inversions & Diminishing Increments, The Ω(N log N) Comparison Lower Bound via Stirling's Approximation
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript or TypeScript against an in-browser Node.js v22 runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

Overview

Musser’s hybrid IntroSort (median-of-three 3-way QuickSort + depth-bounded HeapSort fallback + small-subarray InsertionSort) paired with linear-time 3-way Quickselect.

Guided Implementation Walkthrough (4 Progressive Steps)

Step 1: Cache-Friendly Subarray Insertion Sort

  • Core Mechanical Concept: Low-Overhead O(N^2) Base Case for Small Partitions (N <= 16)
  • Target Module: index.js (insertionSortRange)
  • Engineering Specification: Implement insertionSortRange(arr, lo, hi, cmp) to sort arr[lo..hi] in place. For subarrays of length $\le 16$, InsertionSort beats recursive QuickSort due to zero recursion overhead and sequential L1 cache hits.
  • Verification Invariant: sorts bounded subarray ranges in place via insertion sort

Step 2: In-Place Subarray HeapSort Fallback

  • Core Mechanical Concept: Guaranteeing O(N log N) Worst-Case When Recursion Depth Exhausts
  • Target Module: index.js (heapSortRange)
  • Engineering Specification: Implement heapSortRange(arr, lo, hi, cmp) over offset lo and length n = hi - lo + 1. Build a max-heap in $O(n)$ using Floyd’s bottom-up siftDown from (n >> 1) - 1 down to 0, then repeatedly swap arr[lo] with arr[lo + end] and siftDown(0, end).
  • Verification Invariant: sorts subarrays in O(N log N) worst-case via in-place HeapSort

Step 3: Median-of-Three & Dijkstra 3-Way Partition

  • Core Mechanical Concept: Collapsing Duplicate Keys in O(N) via [ < pivot | == pivot | > pivot ]
  • Target Module: index.js (partition3Way)
  • Engineering Specification: Implement partition3Way(arr, lo, hi, cmp) returning [lt, gt]. Maintain [lo..lt-1] < pivot, [lt..i-1] == pivot, [i..gt] unclassified, and [gt+1..hi] > pivot. When i > gt, return [lt, gt].
  • Verification Invariant: partitions duplicate-heavy inputs into 3 regions and runs full IntroSort

Step 4: Linear-Time 3-Way Quickselect

  • Core Mechanical Concept: Pruning One Partition per Step to Find the k-th Order Statistic in O(N)
  • Target Module: index.js (quickselect)
  • Engineering Specification: Implement quickselect(arr, k, cmp) using partition3Way. If k >= lt && k <= gt, work[k] is in the equal-pivot band—return it immediately! Otherwise recurse/loop into [lo, lt - 1] if k < lt, or [gt + 1, hi] if k > gt.
  • Verification Invariant: selects exact k-th order statistics in expected O(N) time

Asymptotic & Memory Layout Guarantees

  • Category: Sorting & Order Statistics
  • Difficulty: Intermediate (~30 minutes)
  • Key Architectural Highlights:
    • Musser IntroSort combining 3-way Dutch National Flag QuickSort, HeapSort, and InsertionSort
    • Depth trap 2*floor(log2 N) guaranteeing worst-case O(N log N) even on killer inputs
    • Expected O(N) Quickselect with 3-way partitioning for duplicate-heavy arrays
  • Tags & Primitives: IntroSort, Dijkstra 3-Way Partition, HeapSort Fallback, InsertionSort, Quickselect

Production Systems Context & Verification

This from-scratch implementation is engineered with zero external dependencies and deterministic verification harnesses. Every internal invariant—from pointer restoration and bitmask addressing to amortized potential bounds and tree height balance—is asserted directly in test.js. Use the interactive browser workbench above to complete the guided steps in Guided Lab mode or inspect and benchmark the complete reference architecture in Full Solution mode.