This looks wrong.
It still sorts.

Grow an ordered prefix by inserting the next item and shifting larger items right.

A small hand of cards, a short list, or the cleanup inside a larger sorting method.

Like arranging a hand of cards. Its simplicity survives inside sophisticated library sorts.

Cost model

O(n²) worst; O(n) sorted

Average-case work

Θ(n²) for uniformly shuffled distinct keys; Θ(n) for ordered input.

Stable?

Yes

Extra memory

O(1)

Evidence / role

Established

The catch. Excellent for small or nearly ordered inputs; quadratic on reversed input.

Use binary search inside the ordered prefix, then shift to create the insertion slot.

Small arrays whose keys are expensive to compare but whose records are cheap to shift.

Fewer comparisons need not mean fewer moves.

Cost model

O(n log n) comparisons; O(n²) moves

Average-case work

Θ(n log n) key comparisons, but Θ(n²) expected shifts on shuffled distinct keys.

Stable?

Yes, with rightmost ties

Extra memory

O(1)

Evidence / role

Variant

The catch. The array still has to make space; binary search does not make this an O(n log n) time array sort.

Scan the unsorted suffix for its minimum, then place it at the boundary.

A teaching baseline when separating the cost of comparisons from the cost of swaps.

You can minimise swaps without minimising comparisons.

Cost model

Θ(n²) comparisons

Average-case work

Θ(n²) comparisons regardless of input order in the standard implementation.

Stable?

No, usual swap version

Extra memory

O(1)

Evidence / role

Established

The catch. At most n−1 nontrivial swaps, but it rescans even already sorted input.

Swap adjacent inverted pairs; repeat passes until no swap occurs.

Teaching local repair and early termination; rarely the first choice for large data.

A large value can cross the array in one pass; a small value can crawl back slowly.

Cost model

O(n²) worst; O(n) with early exit

Average-case work

Θ(n²) on uniformly shuffled distinct keys; early exit helps ordered input.

Stable?

Yes

Extra memory

O(1)

Evidence / role

Established

The catch. Useful for explaining local repair, usually a poor general-purpose implementation.

Alternate forward and backward bubble passes.

A teaching comparison with bubble sort when small values need to travel left as well as large values right.

Also called bidirectional bubble sort. The return trip repairs the small-value crawling problem.

Cost model

O(n²) worst

Average-case work

Quadratic on typical random permutations; favourable inputs can be cheaper.

Stable?

Yes

Extra memory

O(1)

Evidence / role

Variant

The catch. Symmetry improves some inputs without changing the quadratic worst case.

Compare values across shrinking gaps, ending with gap-one passes until no swaps occur.

A study of whether moving distant inversions early reduces later adjacent swaps on the same input.

Dobosiewicz described a precursor; Box and Lacey published their account in Byte.

Cost model

O(n²) worst

Average-case work

Depends on input distribution and the shrink policy; the displayed quadratic worst-case bound is not an average.

Stable?

No

Extra memory

O(1)

Evidence / role

Established

The catch. Unlike Shellsort, each gap gets a bubbling pass rather than a complete insertion sort.

Move forward if neighbours are ordered; otherwise swap and step backward.

A compact way to express insertion-like repair using a cursor that walks forward and backward.

Sarbazi-Azad called its precursor Stupid Sort. Grune used the garden-gnome name.

Cost model

O(n²) worst; O(n) sorted

Average-case work

Θ(n²) on random permutations; linear on already ordered input.

Stable?

Yes

Extra memory

O(1)

Evidence / role

Established

The catch. An insertion-sort idea expressed as a walking cursor; naming history is not a single clean invention date.

Insertion-sort interleaved subsequences, shrinking the gap until it reaches one.

An array sort with constant auxiliary storage, when the selected gap sequence suits the workload.

Named for Donald Shell, not a shell-shaped data structure.

Cost model

Depends on gap sequence

Average-case work

Depends on the gap sequence as well as the distribution of inputs.

Stable?

No

Extra memory

O(1)

Evidence / role

Established

The catch. Different gaps give different bounds. A single universal O(n log n) label would be misleading.

Sort two parts and repeatedly take the smaller front item to merge them.

Combining already ordered runs, such as batches of dated records. External variants stream them from storage.

Early electronic-computing discussions by von Neumann already treated sorting as a fundamental workload.

Cost model

O(n log n)

Average-case work

Θ(n log n) for standard merge sort; run-aware variants can do less work.

Stable?

Yes, with left-first ties

Extra memory

O(n), usual arrays

Evidence / role

Established

The catch. Predictable growth; the usual array implementation buys easy merging with extra memory.

Merge runs of length one, then two, then four, continuing iteratively.

A merge-based implementation that should use iterative passes rather than recursive calls.

Recursion is a way to describe divide-and-conquer, not a requirement for implementing it.

Cost model

O(n log n)

Average-case work

Θ(n log n) for the conventional fixed merge schedule.

Stable?

Yes

Extra memory

O(n), usual arrays

Evidence / role

Variant

The catch. The merge schedule is fixed and normally ignores existing long runs.

Recognise already ordered runs and merge them rather than starting from singletons.

A collection already organised into ascending runs, where recognising those runs avoids rebuilding all order.

Real data often brings some of its own order.

Cost model

O(n log r) with pairwise merge passes; O(n) for one run

Average-case work

Depends on the number and lengths of runs and the merge schedule.

Stable?

Yes, with careful ties

Extra memory

O(n), common implementation

Evidence / role

Variant

The catch. Run detection and the order of merges determine how effectively that structure is used.

Choose a pivot, partition around it, then sort the resulting regions.

General-purpose in-memory sorting when fast partitions are useful; robust libraries add safeguards.

Hoare developed the idea while studying in Moscow and thinking about Russian-to-English translation.

Cost model

Expected O(n log n); O(n²) worst

Average-case work

Expected Θ(n log n) with random pivots or uniformly shuffled distinct input.

Stable?

No, usual partition

Extra memory

O(log n) typical stack; O(n) naive worst

Evidence / role

Established

The catch. Bad pivot splits can repeatedly leave almost the whole problem unsolved.

Partition into values smaller than, equal to, and larger than the pivot.

A list containing many repeated keys, where equal values can be removed from further recursive sorting.

Equal values become a finished middle region instead of being needlessly sorted again.

Cost model

Expected O(n log n); O(n²) worst

Average-case work

Expected O(n log n), often less with many equal keys; pivot assumptions matter.

Stable?

No

Extra memory

Stack-dependent

Evidence / role

Variant

The catch. Especially instructive on many duplicates; pivot quality still matters.

Two pivots create three regions that are sorted recursively.

An implementation study of partitioning into three regions and the memory scans those partitions require.

Yaroslavskiy’s variant entered Java’s primitive-array sorting implementation.

Cost model

O(n²) for basic form; hybrids differ

Average-case work

Depends on pivot selection, duplicates and the surrounding hybrid implementation.

Stable?

No

Extra memory

Stack-dependent

Evidence / role

Established

The catch. Two pivots are not automatically better: partition costs, memory scans and safeguards matter.

Build a max-heap, move its root to the end, then repair the smaller heap.

A bounded worst case with little workspace, or a fallback when quicksort partitions go badly.

A priority queue becomes a full sorting procedure when you repeatedly remove its winner.

Cost model

O(n log n) worst

Average-case work

O(n log n); the worst-case guarantee is its main attraction, not one measured average.

Stable?

No

Extra memory

O(1), iterative array form

Evidence / role

Established

The catch. Reliable worst case and little extra storage; heap navigation has different locality from sequential merging.

Use a forest of Leonardo heaps to retain useful order while selecting maxima.

A memory-constrained setting where adaptation to existing order is worth more involved heap bookkeeping.

Dijkstra designed a heapsort relative that transitions smoothly toward linear work on ordered data.

Cost model

O(n log n) worst; O(n) best

Average-case work

Depends on pre-existing order; its best and worst bounds describe different ends of that range.

Stable?

No

Extra memory

O(1) words

Evidence / role

Established

The catch. The bookkeeping is considerably more intricate than ordinary heapsort.

Insert values into a search tree and read them in order.

Records being inserted into an ordered search structure that will later be traversed in key order.

It shifts the sorting problem into maintaining an ordered data structure.

Cost model

O(n log n) balanced; O(n²) unbalanced

Average-case work

Depends on the tree’s balancing policy and insertion order.

Stable?

Implementation-dependent

Extra memory

O(n)

Evidence / role

Established

The catch. A plain unbalanced tree can degenerate into a chain. Duplicate storage must preserve all items.

Compare pairs up a tournament tree; emit the winner and replay its path.

Repeatedly selecting the next record while retaining comparisons from earlier rounds in a tournament tree.

Only the matches affected by removing a winner need to be played again.

Cost model

O(n log n)

Average-case work

O(n log n) is also an upper bound on average work in the usual tournament-tree model.

Stable?

Implementation-dependent

Extra memory

O(n), tournament tree

Evidence / role

Established

The catch. The extra tree records reusable comparison results instead of starting each minimum scan anew.

Find destinations and rotate items around permutation cycles.

A situation where overwriting records is expensive and reducing writes is worth extra comparisons.

Haddon studied cycles under conditions allowing linear sorting; the common teaching variant spends comparisons finding ranks.

Cost model

O(n²) for comparison-ranked variant

Average-case work

Depends on how destination ranks are obtained; the common comparison-ranked variant spends quadratic work finding them.

Stable?

No

Extra memory

O(1), common cycle variant

Evidence / role

Established

The catch. Minimal writes and minimal comparisons are different goals. The original paper’s linear claim has assumptions.

Deal values onto ordered piles, then merge their top values.

Reasoning about card piles and the length of an increasing subsequence, with a merge stage for full sorting.

A card-game viewpoint connects sorting to the longest increasing subsequence.

Cost model

O(n log n) with efficient pile search/merge

Average-case work

Depends on the pile structure and the search/extraction implementation; the efficient version has O(n log n) total work.

Stable?

Implementation-dependent

Extra memory

O(n)

Evidence / role

Established

The catch. Building piles alone does not emit a globally sorted list; extraction or merging still matters.

Pull an increasing strand out of the input, merge it into the output, and repeat.

A linked-list exercise in removing increasing subsequences and merging them into an accumulated output.

A linked list lets the procedure remove a strand without shifting an entire array.

Cost model

O(n²) worst

Average-case work

Depends on how long the extracted strands are and how they are merged.

Stable?

Can be stable

Extra memory

O(n), list representation

Evidence / role

Established

The catch. Ordered inputs are friendly; many short strands can force repeated scanning and merging.

Pair elements, order the larger partners, then insert the smaller ones in a carefully chosen schedule.

Small inputs whose comparisons are expensive enough to justify a carefully scheduled insertion process.

A classic attempt to squeeze out comparisons, with special relevance to small input sizes.

Cost model

O(n log n) comparisons

Average-case work

The classic objective is worst-case comparison count; average comparisons require an input model.

Stable?

Usually no

Extra memory

O(n), common implementations

Evidence / role

Established

The catch. Comparison counts are the objective; bookkeeping can outweigh savings in elapsed time.

Count occurrences, compute output positions and place each record into its slot.

Dense integer categories such as a bounded score range, if the count array fits comfortably in memory.

Knowing the key universe substitutes direct addressing for pairwise comparison.

Cost model

O(n + k), k key range

Average-case work

Θ(n + k) in the standard dense-count implementation; k is the key range.

Stable?

Yes, output-buffer form

Extra memory

O(n + k)

Evidence / role

Established

The catch. A huge sparse range makes the count array expensive, even if there are few input items.

Sort by the least significant digit, then by each more significant digit using stable passes.

Digit-structured identifiers. Punched-card processing provides a historical physical analogue.

Physical card sorting helps explain why digit-by-digit ordering predates electronic programs.

Cost model

O(d(n + b)), d digits, base b

Average-case work

Θ(d(n + b)) for fixed-width keys and counting-based digit passes.

Stable?

Yes, stable passes

Extra memory

O(n + b)

Evidence / role

Established

The catch. It relies on key representation and stability. Digit width and sign handling are part of the algorithm.

Group by the most significant digit and recursively refine each group.

Strings or identifiers sharing prefixes, where later characters matter only inside tied groups.

A shared prefix lets whole strings travel together before their next character matters.

Cost model

Key-length, radix and recursive-bucket dependent

Average-case work

Depends on shared prefixes, key lengths, radix and how each recursive bucket is processed.

Stable?

Implementation-dependent

Extra memory

Implementation-dependent

Evidence / role

Established

The catch. Short strings need an end marker; empty and highly uneven buckets require care.

Distribute values into ordered ranges, sort within each range and concatenate.

Numeric keys with a known useful distribution, so ordered ranges can divide the work into small local sorts.

The shape of the data can be useful information.

Cost model

Expected O(n + k) with suitable distribution; O(n²) possible

Average-case work

Expected linear work needs an appropriate distribution and bucket count; a crowded bucket changes the cost.

Stable?

Implementation-dependent

Extra memory

O(n + k)

Evidence / role

Established

The catch. The usual linear expectation assumes balanced buckets and cheap internal work; one crowded bucket changes everything.

Count bucket sizes first so each bucket receives an exact output range.

A distribution pipeline that must know each bucket’s size before assigning contiguous output space.

Sizing the destinations before moving records avoids guessing capacity.

Cost model

Distribution and local-sort dependent

Average-case work

Depends on bucket occupancy and the method used to finish each bucket.

Stable?

Implementation-dependent

Extra memory

Bucket-count dependent

Evidence / role

Variant

The catch. Histogram construction is only one stage; items within a bucket may still need sorting.

Allocate a hole for each possible key and collect records in key order.

Records whose integer keys occupy a small range and can be collected into one container per possible key.

It makes the range of possible values visible as a physical storage cost.

Cost model

O(n + k)

Average-case work

The usual scan-and-collect procedure costs O(n + k) for all inputs in the stated key range.

Stable?

Can be stable

Extra memory

O(n + k) for records

Evidence / role

Variant

The catch. A counting-style technique; storing whole records in holes differs from storing only frequencies.

Count digit buckets and use cyclic moves to permute items into contiguous bucket regions.

Digit-based grouping where a full second record array is undesirable and stability is not required.

An in-place relative of radix sorting, named by analogy with multi-colour partitioning.

Cost model

Key-length dependent

Average-case work

Depends on key lengths, radix and the distribution of prefixes.

Stable?

No, usual in-place form

Extra memory

Bucket counters plus stack

Evidence / role

Established

The catch. Saving a full output array makes the permutation logic harder; stability is normally lost.

Estimate value classes, permute into classes, then clean up the local order.

Numeric data where interpolation yields useful classes and the subsequent cleanup stays inexpensive.

Neubert published the method at euroFORTH and in Dr. Dobb’s Journal.

Cost model

O(n) under suitable distributions; O(n²) possible

Average-case work

Its favourable distribution assumptions govern class balance and cleanup work.

Stable?

No

Extra memory

O(m), m classes

Evidence / role

Established

The catch. Interpolation needs useful value ranges; skew and the cleanup method determine actual performance.

Combine radix-style distribution with comparison sorting for appropriate subproblems.

Numeric or string keys for which radix partitioning can cooperate with comparison-sort fallbacks.

Steven Ross’ work became part of Boost.Sort.

Cost model

Key-width and hybrid dependent

Average-case work

Depends on the key representation and the hybrid’s choice between distribution and comparisons.

Stable?

No

Extra memory

Variant-dependent

Evidence / role

Established

The catch. Numeric representation, range and fallback thresholds matter; the name is not a guarantee of beating every comparison sort.

Begin with quicksort; switch to heapsort if recursion grows too deep.

General-purpose library sorting that needs both quicksort-like speed and worst-case protection.

Musser turned an algorithm’s own behaviour into a signal to change strategy.

Cost model

O(n log n) worst

Average-case work

Input and pivot strategy affect typical work; the O(n log n) worst bound also bounds average work.

Stable?

No

Extra memory

O(log n) stack

Evidence / role

Established

The catch. It retains quicksort’s practical appeal while placing a bound on pathological partitions.

Find natural runs, extend short ones and merge while respecting a scheduling policy.

Data arriving as several already ordered runs, such as concatenated sorted batches.

Tim Peters’ design treats pre-existing order as a resource.

Cost model

O(n log n) worst; O(n) ordered

Average-case work

Depends on existing run lengths, repeated keys and the merge policy.

Stable?

Yes

Extra memory

O(n) worst

Evidence / role

Established

The catch. The original merge policy and current CPython’s Powersort policy should not be conflated.

Choose a nearly optimal merge tree from the positions and lengths of adjacent runs.

Stable library sorting that should preserve and efficiently combine existing runs.

Munro and Wild’s policy is documented in CPython’s list-sort implementation.

Cost model

O(n log n) worst; adapts to runs

Average-case work

Depends on the lengths of detected runs; the merge schedule is designed to use that structure.

Stable?

Yes

Extra memory

O(n), buffered merge

Evidence / role

Established

The catch. It improves how runs are combined, not the definition of a comparison or a universal CPU speed limit.

Peek around the middle to find runs and recursively organise their merges.

A run-aware stable sort whose merge schedule is constructed recursively around runs near a midpoint.

Introduced alongside Powersort as another way to use existing runs well.

Cost model

O(n log n) worst; adapts to runs

Average-case work

Depends on the run-length structure discovered around recursive midpoints.

Stable?

Yes

Extra memory

O(n), buffered merge

Evidence / role

Established

The catch. Similar objective, different merge-tree construction. “Adaptive” needs a specified measure of order.

Extend run-aware merge scheduling to combine more than two runs at a time.

An investigation of merging several existing runs together to reduce data transfers across merge levels.

The research targets data transfers as well as comparisons.

Cost model

O(n log n) work, fixed merge arity

Average-case work

Depends on run lengths and merge arity; the fixed-arity worst bound also bounds average work.

Stable?

Yes

Extra memory

O(n), buffered implementation

Evidence / role

Research

The catch. Results for a four-way implementation describe tested workloads, not a universal multiplier.

Use keys inside the array as workspace for block merging.

Stable array sorting when an external record buffer is unavailable and internal block management is acceptable.

Andrey Astrelin’s implementation pursues stability and constant external memory together.

Cost model

O(n log n) worst

Average-case work

Input structure and internal buffer availability affect work within the stated worst-case bound.

Stable?

Yes

Extra memory

O(1) without external buffer

Evidence / role

Established

The catch. Internal buffers and duplicate handling make the implementation more complex than textbook merge sort.

Merge blocks using a small internal working area rather than a full second array.

A stable block-merge implementation for exploring the cost of replacing large buffers with rotations and searches.

Mike Wikström’s implementation demonstrates a practical stable block-sort approach.

Cost model

O(n log n) worst

Average-case work

Rotations, searches, duplicates and optional caching affect work within its worst-case bound.

Stable?

Yes

Extra memory

O(1) external workspace

Evidence / role

Established

The catch. Constant extra space is not free: rotations, searches and block bookkeeping still cost work.

Detect bad partitions and useful order, disturb patterns and fall back when necessary.

General-purpose unstable sorting that should recognise or disrupt patterns leading to bad partitions.

Orson Peters’ pdqsort explicitly fights inputs that repeatedly fool pivot selection.

Cost model

O(n log n) worst

Average-case work

Typical work depends on detected patterns and duplicates; safeguards provide the stated worst bound.

Stable?

No

Extra memory

O(log n) stack

Evidence / role

Established

The catch. Some branchless benefits depend on cheap comparisons and the type being sorted.

Record partition decisions in blocks before moving the misplaced elements.

A processor-sensitive implementation where reducing unpredictable branches can justify partition buffers.

Edelkamp and Weiss target branch mispredictions, a cost hidden by a simple comparison count.

Cost model

O(n log n) expected; safeguard-dependent worst

Average-case work

Expected bounds depend on pivot assumptions; processor effects are separate from asymptotic work.

Stable?

No

Extra memory

Block buffers plus stack

Evidence / role

Established

The catch. Same broad quicksort idea, different interaction with a modern processor.

Build small ordered groups and use a four-way merging strategy.

A stable merge design whose four-way merge organisation can be evaluated against ordinary two-way merging.

Igor van den Hoven’s implementation emphasises predictable comparison and movement patterns.

Cost model

O(n log n) worst

Average-case work

Depends on input structure and merge behaviour; use its implementation-specific measurements for elapsed time.

Stable?

Yes

Extra memory

O(n), default buffer

Evidence / role

Established

The catch. Repository benchmarks are author experiments; speed depends on data types, compiler and hardware.

Use adaptive analysis and stable partitioning with merging machinery.

Stable sorting where a record buffer is available and adaptive partitioning can cooperate with merging.

A stable quicksort/mergesort hybrid from van den Hoven.

Cost model

O(n log n) worst, documented hybrid

Average-case work

Depends on how analysis divides work between stable partitioning and merging.

Stable?

Yes

Extra memory

O(n), default buffer

Evidence / role

Established

The catch. This is a concrete engineered combination, not proof that either parent family has become obsolete.

Pursue the partitioning approach with limited workspace and without stability.

An unstable partitioning design when limiting workspace is more important than preserving equal-key order.

Related to Fluxsort, with a different memory and stability tradeoff.

Cost model

O(n log n) worst, documented hybrid

Average-case work

Depends on partition balance and which adaptive or fallback paths are taken.

Stable?

No

Extra memory

O(log n), bounded partition machinery

Evidence / role

Established

The catch. Use the implementation’s own guarantees and benchmarks rather than assuming a sibling has identical properties.

Combine adaptive merging with stable quicksort and delayed merge decisions.

Stable sorting of data that may offer both useful runs and repeated keys for a hybrid to exploit.

Peters’ implementation draws on both run structure and duplicate-aware partitioning.

Cost model

O(n log n) worst

Average-case work

Depends on useful runs, repeated keys and the interaction between partitioning and merging.

Stable?

Yes

Extra memory

O(n) worst

Evidence / role

Established

The catch. Its practical behaviour depends on more than a single textbook recurrence.

Combine stable quicksort with merging and detection of useful existing order.

The stable slice-sorting role described in Rust’s 1.81 release, where equal-key order must be preserved.

Rust 1.81 adopted driftsort for stable slice sorting.

Cost model

O(n log n) worst

Average-case work

Depends on input order, repeated keys and the chosen small-input or hybrid path.

Stable?

Yes

Extra memory

O(n) worst

Evidence / role

Established

The catch. An adoption date, not a claim that the entire design was invented on release day.

Combine quicksort’s fast partitions with safeguards and specialised small-input handling.

The unstable slice-sorting role described in Rust’s 1.81 release, allowing equal-key order to change.

Rust 1.81 adopted ipnsort for unstable slice sorting.

Cost model

O(n log n) worst

Average-case work

Depends on duplicates and partition behaviour; the library’s safeguards bound adverse cases.

Stable?

No

Extra memory

O(log n) stack

Evidence / role

Established

The catch. Stable and unstable library APIs promise different behaviour for equal keys.

Build sequences rising then falling, then compare across distances to merge them.

A fixed comparison schedule suited to studying parallel rounds or hardware-like comparator organisation.

A fixed wiring diagram can run many independent comparisons at once.

Cost model

O(n log² n) comparators; O(log² n) depth

Average-case work

The standard network’s comparison count is fixed by input size, independent of input order.

Stable?

No

Extra memory

Network/implementation-dependent

Evidence / role

Established

The catch. Depth measures parallel stages, not the total work of all comparators.

Recursively merge odd and even positions, then repair neighbouring outputs.

A comparison network that should use a fixed recursive merging schedule, independent of observed key values.

A second classic Batcher construction with a predetermined comparison schedule.

Cost model

O(n log² n) comparators; O(log² n) depth

Average-case work

The fixed network performs the same comparator schedule for every allowed input of a given size.

Stable?

No, usual network

Extra memory

Network-dependent

Evidence / role

Established

The catch. It is different from the adjacent odd-even transposition algorithm.

Alternate disjoint pairs (0,1),(2,3) and (1,2),(3,4).

A nearest-neighbour model where disjoint adjacent comparisons can happen in the same round.

Bubble-like local movement arranged so independent neighbours can work simultaneously.

Cost model

O(n²) work; O(n) parallel stages

Average-case work

A fixed-round network ignores input order; an early-exit sequential variant can do less work.

Stable?

Yes, strict adjacent swaps

Extra memory

O(1) sequential extra space

Evidence / role

Established

The catch. More processors reduce elapsed stages but do not erase total quadratic work.

Use expander-based constructions to obtain an asymptotically shallow sorting network.

Understanding the theoretical possibility of logarithmic parallel depth, rather than choosing a simple practical sort.

Ajtai, Komlós and Szemerédi showed that logarithmic-depth sorting networks exist.

Cost model

O(n log n) size; O(log n) depth

Average-case work

Network size and depth depend on n, not on a probability distribution of input order.

Stable?

Not generally

Extra memory

Circuit-dependent

Evidence / role

Established

The catch. An asymptotic existence result does not imply an attractive small-input implementation.

Sample splitter keys, distribute values into ordered buckets, then sort each bucket.

Partitioning work between processors using sampled boundaries, provided buckets remain sufficiently balanced.

Once bucket boundaries are correct, workers can sort their regions independently.

Cost model

Expected O(n log n); balance-dependent

Average-case work

The expected bound depends on sampling and sufficiently balanced bucket occupancy.

Stable?

Usually no

Extra memory

Implementation-dependent

Evidence / role

Established

The catch. Sampling, skew and duplicate treatment determine whether work is balanced.

Use in-place block distribution and branchless splitter trees for parallel samplesort.

Parallel in-place engineering where block buffers, locality and balancing work across threads matter.

Axtmann and colleagues make memory locality and load balancing central design concerns.

Cost model

Expected O(n log n) work

Average-case work

Expected work depends on its sampling model; actual throughput also depends on processor and memory behaviour.

Stable?

No

Extra memory

Per-thread/block buffers

Evidence / role

Established

The catch. “In-place” in parallel engineering can still include bounded buffers per worker.

Sort chunks that fit in memory, write ordered runs, then stream a multiway merge.

A file or database export too large for RAM, where sequential reads and writes are valuable.

When data exceeds RAM, transfers to storage become part of the algorithm’s cost.

Cost model

I/O-dependent; O(n log n) comparison work

Average-case work

Depends on initial runs, RAM, fan-in and external transfers, not just an average comparison count.

Stable?

Can be stable

Extra memory

Bounded RAM plus external output

Evidence / role

Established

The catch. The number of passes and available buffers can matter more than a small comparison saving.

Distribute runs unevenly among input tapes and rotate which tape receives output.

A sequential-storage situation with a limited number of tape-like streams and a need to schedule merge passes.

A design shaped by a limited number of sequential-access storage devices.

Cost model

Run-schedule and device dependent

Average-case work

Depends on initial run lengths, tape count and the sequence of merge passes.

Stable?

Can be stable

Extra memory

Multiple external streams

Evidence / role

Established

The catch. Its cleverness addresses a particular I/O model; it is not a universal modern in-memory sort.

Recursively merge through buffered funnels at several scales.

Studying cache-efficient sorting without supplying the algorithm with the cache’s specific size.

A cache-oblivious design seeks good transfers without being told cache sizes.

Cost model

O(n log n) work; cache-efficient model

Average-case work

Comparison work and expected elapsed time are distinct; its transfer guarantee uses a specified cache model.

Stable?

Can be stable

Extra memory

O(n)

Evidence / role

Established

The catch. The theoretical I/O guarantee assumes the paper’s cache model and tall-cache condition.

Move the largest remaining pancake to the top, then flip it to the bottom.

A constrained-move puzzle: useful for learning to design a procedure around operations you are allowed to use.

Bill Gates coauthored a paper on bounds for sorting by prefix reversal.

Cost model

O(n²) for basic max-and-flip method

Average-case work

The basic method scans every unfinished prefix for its maximum, giving quadratic comparisons. The number and lengths of flips depend on the input.

Stable?

No

Extra memory

O(1), iterative flips

Evidence / role

Exact curiosity

The catch. Their bounds research is not the same as inventing the puzzle. Only prefix reversals are legal moves.

Represent nonnegative integers as rows of beads; let the beads settle into ordered row lengths.

A physical-model thought experiment about representing positive integers as beads and accounting for the apparatus.

Arulanandham, Calude and Dinneen explored a physical model of sorting.

Cost model

Depends on physical vs simulated model

Average-case work

Depends on the physical or simulated model, maximum value and representation cost.

Stable?

Not meaningful for bare counts

Extra memory

May require O(n·M) cells

Evidence / role

Model-specific

The catch. A fast physical settling step does not include all encoding, hardware or simulation costs; M is the maximum value.

Randomly shuffle and check whether the result is ordered. Repeat.

A counterexample showing that eventually finding an answer is very different from having a practical procedure.

A correct sorted result can come from an absurdly unhelpful search strategy.

Cost model

Expected Θ(n·n!) for shuffle/check; unbounded worst

Average-case work

With independent uniform shuffles of n distinct keys, success probability per attempt is 1/n!; expected attempts are n!.

Stable?

No

Extra memory

O(1) shuffle workspace

Evidence / role

Randomised curiosity

The catch. Uniform independent shuffles eventually succeed with probability one, but have no finite worst-case attempt bound.

Sort the first two thirds, the last two thirds and the first two thirds again.

A recursion exercise that exposes the cost of solving overlapping subproblems repeatedly.

Overlapping recursive work turns a simple idea into a very expensive one.

Cost model

O(n^2.71), approximately

Average-case work

The standard recursion follows the same size-dependent structure regardless of input order.

Stable?

No

Extra memory

O(log n) recursion

Evidence / role

Exact curiosity

The catch. The exponent is log(3)/log(3/2). A divide-and-conquer shape alone does not promise efficiency.

Recursively find maxima in two halves, put the larger last, then sort the remaining prefix again.

A deliberate inefficiency example for learning to analyse recursive work rather than judging code by its length.

Broder and Stolfi inverted the usual optimisation objective in their pessimal-algorithms work.

Cost model

Superpolynomial in standard analysis

Average-case work

The deliberately repeated recursive structure controls its large cost; measured averages do not make it practical.

Stable?

No

Extra memory

Implementation-dependent

Evidence / role

Exact curiosity

The catch. It deliberately repeats work; a concise recursive definition need not be fast.

Start a timer for each value and emit when it wakes.

A thought experiment about clocks, parallel tasks and hidden scheduling costs.

It tries to turn numeric order into waking order.

Cost model

Delay depends on values and scheduling

Average-case work

Delays depend on values and scheduling jitter; there is no dependable general sorting-time guarantee.

Stable?

No guarantee

Extra memory

Tasks/timers proportional to input

Evidence / role

Not a reliable general sort

The catch. Real timers jitter, task starts differ and negatives need handling. The scheduler has inherited much of the problem.

Discard each value smaller than the last retained one.

A counterexample for testing specifications. Deletion is valid filtering, but is not full sorting.

The joke exposes a missing requirement: a sorted-looking output can lose data.

Cost model

O(n) filtering

Average-case work

The one-pass filter performs linear work but does not preserve the full input.

Stable?

Keeps surviving order

Extra memory

O(1) possible

Evidence / role

Filtering, not full sorting

The catch. It produces a nondecreasing subsequence, not a permutation of the full input. A merge-based repair would be a different algorithm.

For every i and every j, swap when A[i] < A[j]. The output is ascending.

Testing an initially surprising loop structure, then explaining its correctness through an ordered-prefix invariant.

Fung found it while deliberately constructing wrong algorithms; the classroom detail is unverified.

Cost model

Exactly n² comparisons

Average-case work

Exactly n² key comparisons on every input of length n, including already ordered input.

Stable?

No

Extra memory

O(1)

Evidence / role

Exact curiosity

The catch. Symmetric-looking loops hide asymmetric progress. It is correct but needlessly quadratic even on ordered input.

Use repeated recursion to intentionally take exponential time.

An intentionally reluctant sorting construction used to explore exponential work rather than reduce it.

Abrahamsen’s paper pursues reluctant sorting, continuing the tradition of deliberately inefficient algorithms.

Cost model

Θ(2ⁿ)

Average-case work

Its deliberately exponential recursion is the object of analysis, not an optimised average workload.

Stable?

Implementation-dependent

Extra memory

Recursive workspace

Evidence / role

Exact curiosity

The catch. This is mathematical humour with a real cost analysis, not a performance recommendation.

Fit a model estimating where a value belongs; distribute it and repair remaining disorder.

Numeric sorting where a learned estimate of rank may guide distribution and repair can restore exact order.

Machine learning helps while sorting the data, unlike AlphaDev’s offline program discovery.

Cost model

Model, distribution and repair dependent

Average-case work

Depends on the distribution, model error, training overhead and cost of repairing misplaced records.

Stable?

No, usual implementation

Extra memory

Model/bucket-dependent

Evidence / role

Research

The catch. Model error, duplicates and training overhead must be included in the workload.

Redesign learned distribution to handle repeated keys more effectively.

Studying how a learned distribution sort handles the repeated keys that challenged its earlier design.

The authors identified high-duplicate inputs as a weakness in the original design.

Cost model

Distribution-dependent hybrid

Average-case work

Depends in particular on repeated-key behaviour as well as prediction and repair cost.

Stable?

No, usual implementation

Extra memory

Model/bucket-dependent

Evidence / role

Research

The catch. A useful example of adversarial data exposing an assumption in a promising algorithm.

Search for correct, low-latency assembly programs for tiny sorting tasks.

Tiny fixed-size subroutines called inside a larger library sort. The learning happens before deployment.

Reinforcement learning found routines incorporated into LLVM’s libc++ sorting code.

Cost model

O(1) for fixed tiny input sizes

Average-case work

Input size is fixed and tiny; useful measurements compare instruction sequences on specified hardware.

Stable?

Routine-dependent

Extra memory

O(1)

Evidence / role

Established

The catch. These are small building blocks. They do not remove the Ω(n log n) comparison lower bound for arbitrary n.

Combine integer-sorting techniques with special treatment of frequent keys.

Parallel integer-sorting research in which representation and frequent keys are part of the computational model.

A theory-and-practice study of sorting integers in parallel.

Cost model

Parallel integer-model bounds

Average-case work

Depends on the integer-key and processor model, including key frequencies.

Stable?

Implementation-dependent

Extra memory

Parallel implementation-dependent

Evidence / role

Research

The catch. Integer representation, duplication and processor model are essential to interpreting its guarantees.

Measure order using richer parameters than input length and adapt partition-based sorting to them.

Studying a formal notion of optimality that depends on richer input parameters than length alone.

Sen’s work asks what it should mean for an algorithm to be universally optimal.

Cost model

Optimality under paper’s parameters

Average-case work

Read the cited paper’s input parameters and optimality definition before comparing averages.

Stable?

Model-dependent

Extra memory

See paper

Evidence / role

Research

The catch. This is a defined theoretical notion, not “fastest for every real-world input”.

Select among sorting strategies using observed properties of the input.

Examining the cited proposal’s strategy-selection rules and the assumptions behind its reported comparisons.

The specific research proposal linked below studies selection between strategies; this label is not a unique name for every adaptive hybrid.

Cost model

Strategy- and assumptions-dependent

Average-case work

Depends on the specific strategies selected and the paper’s workload assumptions.

Stable?

Chosen-strategy dependent

Extra memory

Chosen-strategy dependent

Evidence / role

Research

The catch. Author-reported comparisons need independent reproduction; do not treat a promising title as a universal guarantee.

Use a binary-quicksort-derived method for signed, unsigned and floating-point representations.

Research on sorting different numeric representations using a binary-quicksort-derived framework.

Guzmán proposes one representation-aware framework for several numeric types.

Cost model

O(wn), w word width, reported

Average-case work

Reported O(wn) bound; actual average timing depends on numeric type and implementation.

Stable?

Not specified here

Extra memory

O(w), reported

Evidence / role

Research

The catch. The reported bound includes word width. Representation and floating-point ordering conventions are not optional details.

Recursively refine value intervals; clean small buckets with insertion sort and fall back when splits fail.

Exploring numeric interval refinement with cleanup and fallback when an interval split does not help.

A 2026 distribution-sort proposal by Sučić, Vitasović and Petrušić.

Cost model

O(n log n) worst, reported

Average-case work

Author-reported benchmark results; no independent average reproduced here.

Stable?

Not specified here

Extra memory

See full implementation/model

Evidence / role

Research

The catch. Benchmark claims are the authors’ results, not reproduced here; read the full paper for workspace accounting.

Use an ordered-set structure to reduce comparison overhead while guaranteeing only linear moves.

Research where moving records is expensive enough to make linear moves a distinct objective.

Xu and Chick focus on moving records as a separate resource from comparing them.

Cost model

n lg n + O(n) comparisons with high probability

Average-case work

The highlighted comparison guarantee is probabilistic; it is not itself an average runtime statement.

Stable?

Not specified here

Extra memory

In-place, paper’s model

Evidence / role

Research

The catch. The near-optimal comparison statement is probabilistic; the paper also gives a distinct worst-case tradeoff.

Study sorting decisions when items arrive in random order under online constraints.

Studying the cited online arrival model; its decisions and objective differ from sorting an available array.

Recent theory explores what arrival assumptions buy an algorithm.

Cost model

Different online model

Average-case work

The expectation is tied to its random-arrival model and online objective.

Stable?

Not a batch stability claim

Extra memory

Model-dependent

Evidence / role

Research

The catch. An online objective is not interchangeable with sorting an already available array. See the model before comparing bounds.