A broad implementation wishlist, not a promise to implement every entry. There is no closed, exhaustive list of sorting algorithms: variants, hybrids, and new algorithms keep appearing. This catalog covers the named sorts in Wikipedia's comparison tables, plus additional variants, networks, and external sorts. Each algorithm name links to its Wikipedia article or the relevant parent article when it has no separate page.
Implementation status checked against the registry on 2026-09-08. Only registered built-ins count as implemented; historical files and custom editor examples do not.
- Columns match the app's
display,stable,best,average,worst,memory, andmethodmetadata, with implementation status and fit added for planning. - Time and auxiliary memory entries use O(...), with the wrapper omitted.
Bounds describe the stated algorithm variant, not measured animation speed.
log² nmeans(log n)². Memory includes recursion, but excludes the input and Audio Sort's recorded frames. Instrumentation can dominate both time and memory. n: item count;k: number of buckets or possible integer keys;d: number of digits per key;b: radix;w: maximum string length. Key comparisons are constant time unless a row explicitly discusses strings, I/O, or a physical model.- Average cases generally assume randomly ordered inputs; distribution sorts need the additional assumptions in their notes. Randomized expected bounds are labeled.
- Stability means preserving the identities and relative order of equal-key items, not just producing the same numeric values. It applies to the specified variant.
Variesmeans a family needs a concrete variant/model before assigning a bound;Not established heremeans this catalog does not claim a verified bound.N/Ameans the property does not apply. These are not zero-cost claims.- Fit is a project assessment: Direct uses comparisons/swaps; Adapt needs buffering, writes, indexing, or additional visualization; Specialized targets a different data/hardware model; Novelty needs strict size and execution limits. Direct does not mean easy or prioritized.
These are the metadata values currently shipped (with notation normalized for reading), not an endorsement of their accuracy. The catalog below describes algorithm properties separately so stale labels do not become requirements for new implementations.
| Name / source | Stable | Best | Average | Worst | Memory | Method |
|---|---|---|---|---|---|---|
| Bubble | Yes | n | n² | n² | 1 | exchanging |
| Cocktail shaker | Yes | n | n² | n² | 1 | exchanging |
| Comb | No | n log n | n² (upper bound) | n² | 1 | exchanging |
| Gnome | Yes | n | n² | n² | 1 | exchanging |
| Heap | No | n | n log n | n log n | log n | heap |
| Insertion | Yes | n² | n² | n² | 1 | insertion |
| Quick | No | n log n | n log n | n² | n | exchanging |
| Selection | No | n² | n² | n² | 1 | selection |
Quick's memory bound includes its worst-case recursive stack; balanced partitions use logarithmic space. Heap also includes its recursive heapify stack. Its linear best case can occur with equal keys; distinct-key analyses commonly give n log n. Insertion scans the entire prefix without an early exit, so this implementation's best case is quadratic despite the usual algorithm's linear best case. Comb uses a 1.3 shrink factor and stores a conservative quadratic average-case upper bound in the chooser, not a claim of a tight average bound.
| Algorithm | Implemented | Stable | Best | Average | Worst | Auxiliary memory | Method | Fit / notes |
|---|---|---|---|---|---|---|---|---|
| Bubble sort | Yes: bubble |
Yes | n | n² | n² | 1 | Exchanging | Direct; early-exit version. |
| Cocktail shaker sort | Yes: cocktail-shaker |
Yes | n | n² | n² | 1 | Exchanging | Direct; bidirectional bubble sort, also called shaker sort. |
| Comb sort | Yes: comb |
No | n log n | Not established here | n² | 1 | Exchanging | Direct; shrinking gaps, then adjacent comparisons; shrink schedule matters. |
| Gnome sort | Yes: gnome |
Yes | n | n² | n² | 1 | Exchanging | Direct; adjacent swaps walking backward after inversions. |
| Odd–even sort | No | Yes | n | n² | n² | 1 | Exchanging | Direct; serial, early-exit version; also called brick sort. |
| Insertion sort | Yes: insertion |
Yes | n | n² | n² | 1 | Insertion | Direct; standard early-exit variant shown; current app scans the full prefix (quadratic best case). |
| Binary insertion sort | No | Yes | n log n | n² | n² | 1 | Insertion | Direct; unconditional binary search; n log n comparisons but quadratic moves. An ordered-tail shortcut gives linear best time. |
| Shellsort | No | No | Varies | Varies | Varies | 1 | Insertion | Direct; choose a gap sequence first. Original halving gaps have quadratic worst time; Pratt gaps give n log² n. |
| Library sort | No | No (randomized version) | n log n | n log n expected | n² | n | Gapped insertion | Adapt; randomized insertion order and reserved gaps; original analysis. |
| Selection sort | Yes: selection |
No | n² | n² | n² | 1 | Selection | Direct; ordinary swap-based variant. Stable shifting is a separate variant. |
| Cycle sort | No | No | n² | n² | n² | 1 | Selection | Adapt; write-minimizing version needs recorded writes, not just swaps; handle duplicate keys. |
| Heapsort | Yes: heap |
No | n (equal keys) | n log n | n log n | 1 iterative; log n recursive | Heap / selection | Direct; catalog distinguishes iterative and current recursive heapify. |
| Smoothsort | No | No | n | n log n | n log n | 1 | Heap / selection | Direct, advanced; Leonardo heaps. Dijkstra's description. |
| Tournament sort | No | Yes with leftmost tie-breaking | n log n | n log n | n log n | n | Selection | Adapt; retain item identities in a tournament tree. |
| Tree sort | No | Yes with ordered duplicate storage | n log n | n log n | n² | n | Tree insertion | Adapt; ordinary unbalanced BST; random distinct-key insertion for average bound. |
| Balanced tree sort | No | Yes with ordered duplicate storage | n log n | n log n | n log n | n | Tree insertion | Adapt; balancing removes the unbalanced-tree worst case. |
| Splaysort | No | Varies | n | n log n | n log n | n | Tree insertion | Adapt; adaptive splay-tree sort; preserve duplicates explicitly. |
| Patience sorting | No | No (usual pile version) | n | n log n | n log n | n | Insertion / selection | Adapt; requires pile construction and a merge to produce a full sort, not only an LIS. |
| Pancake sort | No | No | n² | n² | n² | 1 | Prefix reversal / selection | Direct; simple repeated maximum scan, not minimum-flip optimization; flips can be swaps. |
| Algorithm | Implemented | Stable | Best | Average | Worst | Auxiliary memory | Method | Fit / notes |
|---|---|---|---|---|---|---|---|---|
| Merge sort (top-down) | No | Yes | n log n | n log n | n log n | n | Merging | Adapt; ordinary array merge with a buffer; no ordered-run shortcut assumed. |
| Merge sort (bottom-up) | No | Yes | n log n | n log n | n log n | n | Merging | Adapt; iterative passes over runs. |
| Natural merge sort | No | Yes | n | n log n | n log n | n | Merging | Adapt; detect runs and use balanced merge passes. |
| In-place merge sort | No | Yes | n | n log² n | n log² n | log n | Rotation / merging | Direct, advanced; recursive rotation-based merge with an ordered-run shortcut; other variants have different bounds. |
| Block sort | No | Yes | n | n log n | n log n | 1 | Block merging | Direct, advanced; constant-buffer variant; WikiSort and GrailSort are related implementations, not extra families here. |
| Timsort | No | Yes | n | n log n | n log n | n | Insertion / merging | Adapt; run detection, merge policy, and galloping. Implementation notes. |
| Powersort | No | Yes | n | n log n | n log n | n | Adaptive merging | Adapt; merge-order strategy combined with buffered merging; original paper. |
| Strand sort | No | Yes | n | n² | n² | n | Selection / merging | Adapt; extracts increasing subsequences, then merges them. |
| Cubesort | No | Yes | n | n log n | n log n | n | Insertion / merging | Adapt, advanced; specialized multi-level structure. |
| Quicksort | Yes: quick |
No | n log n | n log n | n² | log n average; n worst | Partitioning | Direct; ordinary two-recursive-call version; smaller-side recursion can bound stack space. |
| Three-way quicksort | No | No | n (equal keys) | n log n | n² | log n average; n worst | Partitioning | Direct; separates less/equal/greater regions; handles duplicate-heavy input well. |
| Dual-pivot quicksort | No | No | Varies | n log n | n² | log n average; n worst | Partitioning | Direct; pivot policy and duplicate handling determine best case; excludes introspective fallback. |
| Introsort | No | No | n log n | n log n | n log n | log n | Partitioning / heap / insertion | Direct, advanced; depth limit triggers heapsort. |
| Pattern-defeating quicksort (pdqsort) | No | No | n | n log n | n log n | log n | Adaptive partitioning / heap | Direct, advanced; author's implementation and bounds. |
| Fluxsort | No | Yes | n | n log n | n log n | n | Partitioning / merging | Adapt; author's implementation. |
| Crumsort | No | No | n | n log n | n log n | log n | Partitioning / merging | Adapt, advanced; fixed scratch buffer plus recursion; author's implementation. |
| Merge-insertion sort (Ford–Johnson) | No | No (ordinary variant) | n log n comparisons | n log n comparisons | n log n comparisons | Varies | Merging / insertion | Adapt, advanced; comparison counts are not total runtime; array insertion may require quadratic moves. |
These need access to keys, not just an opaque comparator. Numeric output must still preserve the original sort objects: rebuilding bare numbers loses identity and makes stability untestable. Bounds assume the key range and digit operations stated here.
| Algorithm | Implemented | Stable | Best | Average | Worst | Auxiliary memory | Method | Fit / notes |
|---|---|---|---|---|---|---|---|---|
| Counting sort | No | Yes (buffered variant) | n + k | n + k | n + k | n + k | Counting | Adapt; bounded integer range; scatter original items, not reconstructed values. |
| Pigeonhole sort | No | Yes with FIFO holes | n + k | n + k | n + k | n + k | Distribution | Adapt; holes retain all original records, including duplicates. |
| Bucket sort | No | Yes with stable buckets | n + k | n + k expected | n² + k | n + k | Distribution / insertion | Adapt; uniform distribution and insertion-sorted buckets; skew can be quadratic. |
| LSD radix sort | No | Yes | d(n + b) | d(n + b) | d(n + b) | n + b | Digit distribution | Adapt; fixed-length keys, stable counting pass per digit; define negative-key handling. |
| MSD radix sort (buffered) | No | Yes | n + b | d(n + b) | d(n + b) | n + bd | Digit distribution | Adapt; early singleton termination; bound includes count arrays along recursive depth. |
| Binary quicksort / radix exchange | No | No | n | nd | nd | d | Bit partitioning | Direct with key access; in-place MSD variant; integer width must be explicit. |
| American flag sort | No | No | n + b | d(n + b) | d(n + b) | bd | Digit distribution | Adapt; in-place bucket permutation; recursive counter storage bound. |
| Flashsort | No | No | n | n + k expected | n² | k | Distribution / insertion | Adapt; uniform numeric distribution for linear expectation; in-place permutation with class counters. |
| Proxmap sort | No | Yes with stable insertion | n | n expected | n² | n | Distribution / insertion | Adapt; linear number of bins and a well-distributed mapping. |
| Interpolation sort | No | Varies | Varies | Varies | Varies | Varies | Distribution | Adapt; family of numeric interpolation schemes; select a concrete version before implementation. |
| Spreadsort | No | No | n | Varies with key width | Varies with key width | Varies | Radix / comparison hybrid | Adapt, advanced; use the Boost variant's key-width-dependent analysis, not an unconditional linear claim. |
| Burstsort | No | Varies | Not established here | Varies | Varies with bucket sorter | Varies | Trie / distribution | Specialized; strings, prefixes, and cache behavior are outside the current numeric-bar model. |
Network rows report serial comparator work, not parallel depth. A fixed network does the same comparisons regardless of input order; its depth can be much smaller. Network memory excludes a precomputed comparator list and assumes an iterative schedule unless noted. External-sort costs should not be compared directly with in-memory time: disk transfers, buffer size, and merge fan-in matter.
| Algorithm | Implemented | Stable | Best | Average | Worst | Auxiliary memory | Method | Fit / notes |
|---|---|---|---|---|---|---|---|---|
| Bitonic sort | No | No | n log² n | n log² n | n log² n | 1 | Compare-exchange network | Direct; basic network assumes a power-of-two size; depth log² n. |
| Batcher odd–even mergesort | No | No | n log² n | n log² n | n log² n | 1 | Compare-exchange network | Direct; not brick sort; power-of-two network, depth log² n. |
| Pairwise sorting network | No | No (ordinary network) | n log² n | n log² n | n log² n | Varies with schedule | Compare-exchange network | Direct, advanced; choose network size and generator. |
| AKS sorting network | No | No stability guarantee | n log n | n log n | n log n | Varies with representation | Compare-exchange network | Specialized; logarithmic parallel depth but impractical constants/construction. |
| Samplesort | No | Varies | Varies | n log n expected serial work | Varies | Varies | Sampling / partitioning | Specialized; depends on sampling, bucket sorter, and processor count; can be demonstrated serially. |
| External merge sort | No | Yes with stable runs/merge | Varies (I/O model) | Varies (I/O model) | Varies (I/O model) | Bounded RAM buffers; external n | External merging | Specialized; disk-backed runs and streaming are absent from this app. |
| Polyphase merge sort | No | Varies with run handling | Varies (I/O model) | Varies (I/O model) | Varies (I/O model) | Buffers plus external runs | External merging | Specialized; tape/run distribution, not a distinct bar-swap primitive. |
| Funnelsort | No | Yes with stable mergers | n log n | n log n | n log n | n | Cache-oblivious merging | Specialized; serial work shown; cache-transfer advantage needs a separate model. |
| Thorup's integer sorting | No | Not established here | Not established here | n log log n expected | Not established here | n | Integer sorting | Specialized; word-RAM research model, not ordinary JavaScript arithmetic costs. |
| Andersson–Hagerup–Nilsson–Raman sorting | No | Not established here | Not established here | n log log n upper bound | n log log n | Not established here | Integer sorting | Specialized; deterministic word-RAM bound; randomized wide-word variants have different assumptions. |
Do not enable unbounded sorts in the main chooser without cancellation, operation/frame budgets, and tiny input limits. A worker alone does not impose a runtime limit; the fallback path can also block the UI. Physical demonstrations need simulations, whose costs are not the physical model's costs.
| Algorithm | Implemented | Stable | Best | Average | Worst | Auxiliary memory | Method | Fit / notes |
|---|---|---|---|---|---|---|---|---|
| Bogosort (random shuffle) | No | No | n | n·n! expected | Unbounded | 1 | Random permutation | Novelty; distinct keys and uniform independent shuffles for expectation. |
| Permutation sort (deterministic bogosort) | No | No | n | n·n! upper bound | n·n! | Varies with enumerator | Permutation enumeration | Novelty; finite only if permutations are enumerated without repetition. |
| Bogobogosort | No | No | Varies | Not established here | Unbounded (randomized) | Varies | Recursive random permutation | Novelty; definitions vary; no useful default input size. |
| Stooge sort | No | No | n^2.7095… | n^2.7095… | n^2.7095… | log n | Recursive exchanging | Novelty; exponent is log(3)/log(3/2); easy to express with swaps. |
| Slowsort | No | No | T(n) | T(n) | T(n) | n | Recursive exchanging | Novelty; T(n) = 2T(n/2) + T(n−1) + O(1), superpolynomial; same recursion for every input order. |
| Bead sort | No | N/A for unlabelled beads | Varies by model | Varies by model | Varies by model | Varies by model | Gravity / unary representation | Specialized; nonnegative integers; grid simulation can require n·max(key) cells, and does not inherently retain record identity. |
| Spaghetti sort | No | N/A without a tie protocol | n physical operations | n physical operations | n physical operations | n rods | Physical selection | Specialized; simultaneous physical comparison is not a constant-time software primitive. |
Cocktail shaker, Gnome, and Comb are implemented. Good next additions are Shell (with a documented gap sequence) and Odd–even: both can show their intermediate work through existing swaps. Bitonic and Pancake add visibly different movement patterns without needing buffers.
Before buffered Merge, Counting, or Radix, decide how the engine should record writes and auxiliary storage. Sorting a hidden copy and replaying only the final permutation would hide the algorithm's actual work. A swap-only adaptation may change its time, space, or write-count properties and should be labeled accordingly.
The fit labels are not permanent exclusions: even external algorithms can be simulated on small inputs, but doing so meaningfully needs a visualization of their actual model. Meme procedures that discard items or simply assume the input is sorted are not valid general sorting implementations; the app requires an ordered permutation of the input.
When adding an algorithm, choose its exact variant, confirm the bounds from its paper or reference implementation, test duplicate-key stability and identity preservation, and update both this catalog and the app metadata. Follow Adding algorithms.