Sorting Algorithms: A Technical Reference Sheet and Comparison Chart

The Algorithms Guide

This is a highly technical and to the point reference sheet and comparison chart about Sorting Algorithms. For a more introductory article check or Sorting Algorithms: A Comprehensive Guide.

Context of Sorting

Within contemporary computer architecture, ordering operations subtend a broad spectrum of computational workflows—index construction, relational joins, external-memory analytics, cache-oblivious layout transformations, and GPU rendering pipelines. Although the asymptotic landscape is ostensibly settled, micro-architectural mismatches can trigger pathological cache-miss cascades, TLB pressure, or write-amplification on non-volatile media. Conversely, a judiciously selected method can brush the linear-time information-entropy bound for favorable input distributions while respecting stringent energy and memory budgets.

Heuristic Decision Framework

Avoid rote complexity tables; instead apply this four-factor calculus:

• Cardinality n — For n < 32 quadratic behavior is inconsequential; 10^4 ≤ n ≤ 10^7 invites O(n log n); beyond core memory, contemplate multi-way external merge.
• Key topology — Bounded integer domains (k ≪ n) imply counting or radix; smoothly distributed [0, 1) floats invite bucketization.
• Memory envelope — Firmware hot-paths or embedded SoCs frequently forbid auxiliary buffers, privileging in-place Quick/Heap.
• Latency certainty — Real-time controllers and HFT micro-services prefer algorithms with tight deterministic upper bounds.

Pragmatic aphorism — When the distribution is opaque and a few kilobytes of scratchpad are acceptable, TimSort or Musser’s introsort offer consistently favorable latency-throughput profiles.

Comparison-Centric Algorithms

Canonical descriptions augmented with historiographic notes and micro-architectural caveats.

Bubble Sort

Origins. Iverson’s APL idioms (1962) catalyzed its didactic debut.
Current status. Pedagogical only; for arrays < 10 locality sometimes offsets its O(n²) cost, but practical alternatives abound.

procedure bubble_sort(A):
    repeat
        swapped ← false
        for i ← 1 → |A|-1 do
            if A[i-1] > A[i] then
                swap A[i-1], A[i]
                swapped ← true
    until not swapped

Selection Sort

Endurance rationale. Exactly two writes per element make it suitable for EEPROM or flash with limited write cycles.

Insertion Sort

Cache intimacy. Linear probing of contiguous cells delivers near-optimal spatial locality; compilers and STL hybrids therefore switch to insertion for sub-arrays ≤ 32.

Shell Sort

Gap-sequence research. Sedgewick, Tokuda, and Pratt sequences empirically converge near O(n^1.25). The algorithm’s in-place nature and low branch-misprediction footprint still justify its niche in legacy embedded toolchains.

Merge Sort

Pointer-level variant. On linked lists, tortoise–hare splitting enables O(1) auxiliary space. Bottom-up blocking harmonizes with SIMD widths and GPU shared-memory tiles.

Quick Sort

Canonical formulation. Hoare’s 1961 two-index partitioning.
Pivot robustness. Median-of-ninther, median-of-medians, or random pivots mitigate adversarial cases.
Introspective safeguard. Musser’s introsort (1997) monitors recursion depth (≈ 2 log₂ n) and falls back to heap sort, enforcing O(n log n) worst-case bounds.

function partition(A, lo, hi):
    pivot ← A[(lo+hi) // 2]  # optional median‑of‑three
    i ← lo; j ← hi
    while true:
        while A[i] < pivot: i ← i+1
        while A[j] > pivot: j ← j‑1
        if i ≥ j: return j
        swap A[i], A[j]
        i ← i+1; j ← j‑1

Heap Sort

Linear-time heapification. Floyd’s bottom-up sift-down eliminates the naïve n log n build.
Locality penalty. Scattered memory accesses degrade cache behavior; quick sort often wins wall-clock unless memory is at a premium.

TimSort

Design synthesis. Peters (2002) merged natural-run detection, binary insertion, and exponential galloping. The min-run heuristic (≈ 32) targets L1 capacity.
Caveat. A 2012 Java port bug (stack collapse when invariants were violated) underscores its subtle invariants.

IntroSort

Starts with quick sort, switches to heap at depth sentinel, and finishes tiny partitions with insertion. std::sort in the C++ STL adopts this tri-modal choreography, combining average-case agility with worst-case certainty.

Distribution-Oriented Algorithms

Counting Sort

Auxiliary memory scales with key domain k; compress sparse domains via perfect hashing or bucket compression first.

Radix Sort

Digit ordering. LSB orientation preserves stability and streamability; MSB orientation yields quick-sort-like partition recursion.
Word-size engineering. On 64-bit integers, 11-bit buckets (2048) need six passes—trading bandwidth for cache occupancy.

Bucket Sort

Effectiveness degrades when the hash deviates from uniformity; sort intra-bucket with insertion or quick sort for resilience.

FlashSort (expository)

Hybrid classification plus insertion achieves quasi-linear time on uniformly distributed floats but enjoys little industrial adoption.

External Sorting Architecture

• Run formation — Stream M-element chunks into RAM, sort internally, flush to disk.
• Polyphase merge — Merge k runs via loser-tree or d-ary heap where k × blockSize ≤ RAM.
• I/O orchestration — Double-buffered, asynchronous DMA hides rotational or SSD latency.
• Distributed scaling — MapReduce, Spark, and Flink replicate this paradigm across cluster topologies.

Complexity Synopsis

Empirical Vignettes

• High-volume log ingest — Streaming 500 GB/day of JSON through external merge with a 64-way loser-tree on NVMe RAID sustains 320 MB/s, a 1.8 × speed-up over two-way merging.
• Mobile address-book ordering — A reactive front-end sorts ≈ 300 records via TimSort; diff-aware run detection cuts median latency to ≈ 250 µs.
• Real-time particle systems — CUDA radix on 1 M elements (32-bit depth keys) executes in ≈ 3 ms per frame on an RTX 4090, exploiting warp-level shuffles and shared-memory histograms.

Operational Heuristics

• Wear-sensitive embedded arrays (n ≤ 32) — Selection sort minimizes write cycles.
• General in-memory primitives — Introsort for POD types; TimSort when stability is required.
• Terabyte-scale pipelines — k-way external merge with LZ4/Parquet compression between passes reduces I/O.
• Bounded integer IDs (< 2^16**)** — Two-pass radix (16-bit chunks) outperforms comparison sorts.
• Incrementally sorted sensor feeds — Amortized O(1) insertions; schedule periodic TimSort consolidation.

Annotated Bibliography

Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, 1998.
Bentley, J. L., & McIlroy, M. D. “Engineering a Sort Function.” Software—Practice & Experience 23 (1993): 1249–1265.
Peters, T. “TimSort: A Very Fast, Hybrid Sorting Algorithm,” PEP 450, 2002.
Blelloch, G. E. et al. “GPU Radix Sort: An Experimental Study.” PPoPP ’16: 556–567.

Back to the Main Algorithms Guide

To go to the main guide about algorithms follow this link: A Friendly Guide to Computer Science Algorithms by Category,