EVOPEDIA

← all systems · see it in The System

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending order or descending order.

Properties published scienceour proposal

Sourced fields, and our own readings.

born at1887 (Hollerith); 1945 (merge sort)
born precisionyear
boundaryInside: the procedure that puts the elements of a list into an order: the key and the order relation it reads, the elementary operations (compare two keys, swap or move an element, read a digit and count it), the method's step (insert, merge, partition around a pivot, take the top of a heap, distribute by digit), its control (recursion, hybrids that switch method by size or depth, adaptivity to existing runs), and the output, a permutation of the input in monotonic order, stable or not, with its cost bounds; together with the practice that designs, analyses, proves, benchmarks and adopts sorts into standard libraries. Outside: the memory and processors it runs on (caches, RAM, disks, GPUs), the libraries and languages that carry it, the data and callers that hand it lists, the people and programs that use sorted output, and the heat the machine sheds while it runs.
nested levelA kind of algorithm (sys:algorithm), carried by machines since the tabulating machine and the stored-program computer (rung 12) and by people sorting by hand (rung 11, sys:human). Its parts are methods (insertion, merging, partitioning, heaps, distribution) combined into hybrids; it sits inside standard libraries (sys:software) that every program calls, and its order relation for text rests on an alphabet's fixed order (sys:alphabet).
scaletechnological

Measures (27) published science

comparison lower boundn log2 n - 1.4427n + O(log n) (log2(n!)) comparisons
fewest comparisons to sort n elements0, 1, 3, 5, 7, 10, 13, 16, 19, 22, 26, 30, ... 71 for n = 1..22 (only these n known) comparisons
dual-pivot quicksort comparisons and swaps1.9 n ln n - 2.46n comparisons; 0.6 n ln n + 0.08n swaps (random permutation, average) operations
fat-pivot quicksort against the optimumwithin a factor of 1.088 on average (ninther pivots) ratio
Timsort worst case in run entropy1.5 nH + O(n) comparisons (H = entropy of run lengths)
Timsort worst-case element moves against mergesortat least 1.5 times
Timsort-drag merge cost30% more than simple non-adaptive mergesort merge cost
powersort against Arrays.sort20% faster than Arrays.sort(int[]) running time
comparisons to detect runsn - 1 comparisons
insertion-sort cutoff in optimized quicksorts16-32 elements
pdqsort bad-partition cutoff0.125 fraction (pivot percentile)
heapsort against quicksort on random dataabout twice as slow running time
IPS4o against earlier in-place parallel comparison sortsalmost a factor of three faster running time
size of the IPS4o benchmark21 codes x 6 data types x 10 distributions x 4 machines x 4 allocation strategies; sizes over 7 orders of magnitude configurations
Onesweep GPU sorting rate29.4 GKey/s (256M random 32-bit keys, NVIDIA A100)
global memory operations per digit-binning pass~2n (Onesweep) against ~3n (two-pass) memory operations
optimal sorting-network size, 9 and 10 inputs25 comparators for 9 inputs (Floyd 1964); 29 for 10 (Waksman 1969); proved optimal 2014
shortest sort-3 program17 instructions (x86 assembly, brute-force proof)
AlphaDev sort improvementsup to 70% (length 5); about 1.7% (over 250,000 elements) speed-up
time between changes to libc++ small sortsover a decade (to 2023) years
library sort generation in Pythonsamplesort hybrid to Timsort 2002; Timsort's merge policy to Powersort 2022 (Python 3.11) years (dates as sourced)
Timsort temporary memoryup to N//2 pointers
samplesort against timsort comparisonsabout 1.5% more comparisons (random arrays)
energy explained by time complexityover 99% of variance (counting, merge, quick sort); over 94% (bubble sort) variance explained
branch mispredictions, random against sorted input900 times more mispredictions
Algotype clustering in chimeric self-sorting arrayspeaks 0.72, 0.65, 0.69, 0.62 (from 0.5) at 42, 21, 19, 22% of the sort aggregation value
seriation onset in childrentypically 7 to 11 years (Piaget); suddenly around 7 (McGonigle-Chalmers and Kusel); most kindergartners 5-6 (others) age, years

Open contentions (5) open contention

Where sources or readings disagree. Both stay on the map.

Partners and parts published science

Built from / builds (5)

Sits inside / holds (3)

Trades with (valence) (12)

expressed by (24)

floor filled by (24)

represents (1)

Kinds (18)

Notes published science

Layers

The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.

sorting: a list in memory put into order (reader's view)

  1. L1: The items to be sorted, held in memory: records in a list or array that can be reached anywhere at once (random access), spilling to disk or swap when too large; for a person, papers, books or cards spread on a table
  2. L2: The key and the order: the part of each record used for sorting (the key), and the order asked for, numerical or lexicographical, ascending or descending; a comparator may use only a subset of the data (sorting cars by their colour)
  3. L3: Elementary operations: compare two keys (at most one bit per comparison), swap or move an element, or read a digit and count it in a bin (distribution sorts)
  4. L4: The method's step: insert into a sorted prefix (insertion), merge two sorted runs (merging), partition around a pivot (quicksort), take the top of a heap (heapsort), distribute by digit into buckets (radix, counting, bucket)
  5. L5: Control: recursion and divide and conquer; hybrids that switch method by size (insertion sort at 16-32 elements or fewer) or by trouble (heapsort after too deep a recursion or too many bad partitions); adaptivity to existing runs; external and parallel schemes
  6. L6: The order produced and what is guaranteed: a permutation of the input in monotonic order; stable or not; in place or not; its cost against the bounds (about n log2 n comparisons for comparison sorts; n times digits for radix sorts)
  7. L7: Use back on the world: sorted lists for search and merging, canonical data, human-readable output, index construction, similar elements brought together, data laid out for locality; library sorts called trillions of times a day

the boardroom (shared floors)

  1. L4: The step: one move of the method built from compares, swaps, moves and counts (insert, merge, partition, heap select, distribute)
  2. L5: Method and control: recursion, divide and conquer, hybrid switching by size or trouble, run merging policy, galloping, fallbacks
  3. L6: The order and its guarantees: permutation in monotonic order, stable or not, in place or not, cost against the bounds
  4. L7: Use: the sorted output put to work (search, merge, indexes, canonical forms, readable output) and the sort adopted into libraries

way in: Benchmarks and proofs fed back to the practice

  1. L1: Runs on real machines and inputs: 21 codes, 6 data types, 10 distributions, 4 machines; 100 machines for latency
  2. L2: Measures: time, comparisons, swaps, merge cost, energy (Intel RAPL)
  3. L3: Analysis and proof: average-case analysis, worst-case proofs, formal verification
  4. L4: Comparison with the prior art and the human benchmarks
  5. L5: Claims tested against each other: claims of the best sort cannot all be true

way in: Existing order in the input (runs)

  1. L1: The input as handed over, often with exploitable partial order in real life
  2. L2: Run detection: maximal increasing or strictly decreasing stretches found with n - 1 extra comparisons; decreasing runs reversed
  3. L3: Run lengths, short runs boosted to a minimum length by binary insertion sort
  4. L4: The run stack: runs pushed and merged so their lengths grow at least like the Fibonacci numbers

way in: Key digits read directly (distribution sorts)

  1. L1: Keys held as integers or strings in memory
  2. L2: One digit taken at a time, from the least significant (LSD) or the most significant (MSD)
  3. L3: The digit counted into its bin; per-block digit histograms on a GPU

way in: Keys read by comparison

  1. L1: The records in memory, one pair addressed at a time
  2. L2: The key of each record (the part used for sorting)
  3. L3: The comparison operator: one abstract comparison of two keys, a total preorder, at most one bit per comparison

way in: Random bits (randomized pivots)

  1. L1: A source of random numbers outside the sort
  2. L2: Random pivot candidates drawn (randomized quicksort); swapped in only after a bad partition in pdqsort's optional mode
  3. L3: The pivot chosen: which element the next partition compares against

way in: The machine's costs (cache, branch prediction, memory hierarchy)

  1. L1: The physical machine: processor pipelines, caches, RAM, disk, GPU global memory
  2. L2: Speeds of the memory levels: comparisons of nearby elements at bus or CPU speed, disk far slower
  3. L3: Costs incurred: cache misses, branch mispredictions (900 times more on random than sorted input), memory traffic (~3n against ~2n per digit pass)
  4. L4: Locality: the number of passes and the localization of comparisons can matter more than the raw number of comparisons
  5. L5: Algorithm engineering against the measured costs: branchless partitioning, blockwise in-place distribution, small code at the bottom

way in: The order asked for by the caller

  1. L1: The calling program or person, who wants the data in an order
  2. L2: The key function or custom comparison supplied (it may use a subset of the data)
  3. L3: The order relation, which must be a total preorder; ascending or descending, numerical or lexicographic

way in: The sort's own progress (inner): recursion depth, bad partitions, merge winners

  1. L1: The run's own state in memory: counters kept on the call stack and in the merge state
  2. L2: Counts: recursion depth (introsort), bad partitions (pdqsort), how many times in a row one run wins the merge (Timsort)
  3. L3: Compared with a threshold: depth limit 1 + 2 floor(log2 n); a partition more unbalanced than p = 0.125; MIN_GALLOP wins
  4. L4: The decision at each recursive call: fall back, use insertion sort, or partition and recurse

way out: A person sorting by hand

  1. L1: Papers, books, cards or sticks moved on a table or floor; moving an object far is the expensive part
  2. L4: Each move: pick an item, compare, place it
  3. L5: The method chosen by hand: insertion for small sets, bucketing by initial letter for large ones, merging with two hands; a child takes the largest first

way out: A sort adopted into a standard library

  1. L1: Library code shipped: Rust's sort_unstable, Python 3.11's list sort, LLVM libc++'s sort 3/4/5, Java 7's primitive sort
  2. L5: An implementation released compatible with the library interface (std::sort)
  3. L6: A sort shown faster or more robust than the one in use

way out: Elements moved back into memory (swaps, moves, writes)

  1. L1: The array rearranged in place, or copied to a temporary buffer (Timsort up to N//2 pointers)
  2. L3: Writes to memory; selection sort uses fewer writes; on new memories a write costs more than a read
  3. L4: The move decided: swap, shift, copy to a merge area, scatter to a bucket

way out: Energy drawn and heat shed by the running machine

  1. L1: Heat irreversibly dissipated into the environment; never zero for logically irreversible steps
  2. L3: CPU energy measured (RAPL); energy follows time complexity
  3. L4: Each step's operations executed by the processor

way out: The sorted list handed back

  1. L1: The list in memory, or human-readable output on paper or screen
  2. L6: A permutation of the input in monotonic order
  3. L7: The order put to use by the caller

Sources (25) published science

Sorting algorithm (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01)
Peters ORL (2021) Pattern-defeating Quicksort. arXiv:2106.05123 (behind its links)
Peters T et al. listsort.txt: design notes for CPython's list sort (timsort; powersort merge policy), CPython repository (behind its links)
Auger N, Jugé V, Nicaud C, Pivoteau C (2018) On the Worst-Case Complexity of TimSort. ESA 2018; arXiv:1805.08612 (behind its links)
Zhang T, Goldstein A, Levin M (2023) Classical Sorting Algorithms as a Model of Morphogenesis: self-sorting arrays reveal unexpected competencies in a minimal model of basal intelligence. arXiv:2401.05375 (behind its links)
Yadav A, Caravelli F, Wolpert D (2024) Entropy production bounds for systems running computer programs. arXiv:2411.16088 (behind its links)
Comparison sort (Wikipedia) (behind its links)
OEIS A036604: Sorting numbers: minimal number of comparisons needed to sort n elements (behind its links)
Wild S, Nebel ME (2012/2013) Average Case Analysis of Java 7's Dual Pivot Quicksort. ESA 2012; arXiv:1310.7409 (behind its links)
Munro JI, Wild S (2018) Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs. ESA 2018; arXiv:1805.04154 (behind its links)
Axtmann M, Witt S, Ferizovic D, Sanders P (2020) Engineering In-place (Shared-memory) Sorting Algorithms. arXiv:2009.13569 (behind its links)
Adinets A, Merrill D (2022) Onesweep: A Faster Least Significant Digit Radix Sort for GPUs. arXiv:2206.01784 (behind its links)
Codish M, Cruz-Filipe L, Frank M, Schneider-Kamp P (2014) Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten). arXiv:1405.5754 (behind its links)
Mankowitz DJ, Michi A, et al. (2023) Faster sorting algorithms discovered using deep reinforcement learning. Nature 618:257-263. doi:10.1038/s41586-023-06004-9 (behind its links)
Timsort (Wikipedia) (behind its links)
Carter K, Ho SMG, Larsen MMA, Sundman M et al. (2023) Energy and Time Complexity for Sorting Algorithms in Java. arXiv:2311.07298 (behind its links)
Tzuriel D, Hanuka-Levi D (2026) Computerized dynamic assessment of seriational thinking modifiability: Effects of mediation on seriation and readiness for math among kindergarten and grade 1 children. Br J Educ Psychol 96(2). doi:10.1111/bjep.70059 (PMC13155057) (behind its links)
Recursion (computer science) (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Blelloch GE, Fineman JT, Gibbons PB, Gu Y (2016) Sorting with Asymmetric Read and Write Costs. arXiv:1603.03505 (behind its links)
Merge sort (Wikipedia) (behind its links)
Quicksort (Wikipedia) (behind its links)
Heapsort (Wikipedia) (behind its links)
Radix sort (Wikipedia) (behind its links)
Oehlschlägel J (2024) Simple Symmetric Sustainable Sorting: the greeNsort article. arXiv:2402.01816 (behind its links)
Shi J, Lyu C (2026) The Role of Eph/Ephrin-Driven Actomyosin Contractility in Promoting Cell Segregation and Boundary Formation. Int J Mol Sci 27(7):3250. doi:10.3390/ijms27073250 (PMC13073651) (behind its links)