Sort Basics

What to Consider When Calling a Sorting API

Most languages ship a sorting API in their standard library. You can leave the algorithm to the API, but the caller still decides what order to sort by, whether the original array may change, and whether equal keys keep their order. These five checks tell you which API to call and how.

1. 1

   Do you need a complete order of every item?

   If you do not need every element in sorted order, consider an API or data structure that fits the goal instead of a full sort.

   • One minimum or maximum → min / max
   • Only the highest or lowest k → top-k (select only the k items you need)
   • Only a median or a boundary such as the top 10% → selection (find the item at a chosen rank)
   • Repeated lookup over the same data → an index or ordered data structure
   • A database query already guarantees the required order → do not sort it again into the same order
2. 2

   Have you decided how null, NaN, text, and ties are ordered?

   Decide whether null comes first or last, how NaN behaves, and which language or region (locale) supplies the rules for ordering text. Decide as well whether items with equal keys stay tied, or whether a second key settles their order.

3. 3

   May the original data be changed?

   If other code refers to the same array, an API that rewrites its input also changes the order that code sees. JavaScript’s items.sort(compare) reorders items itself and returns that same array, so const ordered = items.sort(compare) still loses the original order. To keep it, use an API that returns a new array (toSorted in JavaScript, added in ES2023, or sorted() in Python).

4. 4

   Must equal keys keep their original order?

   Requirements such as showing tied scores in signup order, or preserving an earlier stage of a multi-key sort, need a stability guarantee. Whether an API gives one varies: C++'s std::sort does not, while std::stable_sort does. Read the guarantee from the API instead of inferring it from an algorithm name.

   To see the guarantee in each language: Standard Sorts Across Languages

5. 5

   Can you afford the working memory and the comparison work?

   Some sorting APIs allocate a work array (out-of-place). Where memory is tight, as on embedded devices, an in-place sort helps, but few in-place sorts are also stable.

   To see how stability and extra memory trade off: Stability and extra memory

   The comparator usually runs many times more often than there are elements (about 10,000 times for 1,000 elements in random order). If each comparison converts strings or parses dates, that work repeats just as often. Compute an expensive key once per element before sorting, for example by building key–element pairs first.

Choosing your own order

Many sorting APIs take a comparator that decides the order. By passing just the comparison you would write in a for loop as a function, you avoid writing the whole sorting procedure yourself. Here are the two ways in JavaScript.

Numbers, smallest first

const nums = [5, 2, 9, 1];
for (let i = 0; i < nums.length - 1; i++) {
  for (let j = 0; j < nums.length - 1 - i; j++) {
    const a = nums[j], b = nums[j + 1];
    if (a > b) {
      nums[j] = b;
      nums[j + 1] = a;
    }
  }
}
// [1, 2, 5, 9]

const nums = [5, 2, 9, 1];
nums.sort((a, b) => a - b);
// [1, 2, 5, 9]

Players, highest score first

for (let i = 0; i < players.length - 1; i++) {
  for (let j = 0; j < players.length - 1 - i; j++) {
    const a = players[j], b = players[j + 1];
    if (a.score < b.score) {
      players[j] = b;
      players[j + 1] = a;
    }
  }
}

players.sort((a, b) => b.score - a.score);

A comparator takes two elements, a and b, and returns a negative number if a comes first, a positive number if b comes first, or 0 if they tie. a - b is positive when a is larger, so it gives the same order as swapping in the loop when a > b.

How you pass a comparator depends on the language. Some APIs, such as C#'s OrderBy, even take a key instead of a comparator.

Keep the comparator consistent

When you write a comparator yourself, follow these three rules.

Keep answers consistent

Comparing the same two elements always gives the same answer. Do not mix in random numbers, the current time, or values that change during the sort. If you swap a and b, the answer must flip too.

No cycles in the order

If a comes before b and b comes before c, then a comes before c. A comparator that switches criteria depending on the pair (by score when both have one, otherwise by name, for example) can go round in a circle: a before b, b before c, and c before a.

Don't break chains of ties

Two elements where neither comes first are tied. If a ties with b and b ties with c, then a ties with c. Treating close values as equal (equal when |a - b| is below a threshold) breaks this rule.

Here is a comparator that breaks each rule, next to a fixed one.

Keep answers consistent

players.sort((a, b) =>
  a.score > b.score ? -1 : 1);

players.sort((a, b) => b.score - a.score);

When two scores are equal, swapping a and b still returns 1, so each element claims the other comes first. The fix returns 0 for equal scores.

No cycles in the order

players.sort((a, b) =>
  a.score != null && b.score != null
    ? a.score - b.score
    : a.name.localeCompare(b.name));

const noScore = (p) => p.score == null;
players.sort((a, b) =>
  noScore(a) - noScore(b)
    || (a.score ?? 0) - (b.score ?? 0)
    || a.name.localeCompare(b.name));

Once some players have no score, the comparator uses scores for some pairs and names for others, so the order can go round in a circle. The fix puts players without a score last, then compares by score and then by name.

Don't break chains of ties

values.sort((a, b) =>
  Math.abs(a - b) < 10 ? 0 : a - b);

values.sort((a, b) =>
  Math.floor(a / 10) - Math.floor(b / 10));

100 ties with 108 and 108 ties with 116, but 100 does not tie with 116. The fix compares in buckets of 10, so every value in the same bucket ties.

The O(n log n) Barrier

General sorting algorithms that determine order through comparisons alone require Ω(n log n) comparisons in the worst case. Therefore, a comparison sort with O(n log n) worst-case time is asymptotically optimal. The stable merge sort and the unstable heapsort are equally optimal in this sense.

Start with a decision tree for three elements

Sort three distinct elements A, B, and C using only less-than comparisons. Each answer is Yes or No, and each leaf is the completed order reached by that path.

In general, n distinct elements have n! possible orders. A binary decision tree of height h has at most 2ʰ leaves, so distinguishing every order requires 2ʰ ≥ n!, or h ≥ ⌈log₂(n!)⌉. This is Θ(n log n), giving a worst-case lower bound of Ω(n log n) comparisons.

To break through this wall, you need information beyond comparisons. Distribution sorts use the values themselves or the shape of the keys to place elements, freeing them from the comparison-based lower bound and enabling sorting faster than O(n log n) under the right conditions. Counting sort and radix sort are the prime examples.

Speed also depends on the shape of the keys. Counting sort is Θ(n + k) for key range k, and LSD Radix Sort is Θ(d(n + b)) for d digits in base b (the number of values one digit can take). Both use keys directly, so they count different work from comparison sorts. A large key range or many digits can make them slower.

The worst-case lower bound for comparison sorting does not change. However, if the input already has parts that are in order, a sort may use them to reduce comparisons and movement. A sort that finishes in linear time on sorted input, and in nearly linear time when only a few elements are out of place, is called an adaptive sort.

Stability and extra memory

Speed is not the only thing to weigh when choosing a sort. How much memory it uses, and whether it keeps the order of equal keys, matter too.

In-place sorting and extra memory

The memory used in addition to the input is the sort's auxiliary space complexity. An in-place sort orders elements by moving them within the original array. That does not mean it uses no extra memory at all. Most need only O(1) working storage, although some implementations use about O(log n) to record recursive calls. An out-of-place sort works through a temporary array, so it needs extra memory, typically O(n).

Embedded devices and other environments with little memory are a typical place where in-place sorts are chosen. There, O(n) extra memory is hard to come by, and sorts that use a temporary array may have to be avoided.

Stability

A stable sort keeps elements with equal keys in the order they started in. When sorting students by score, a stable sort keeps “Tom” and “Sam” (both 90) in their original order.

This matters when the key is only part of each element, rather than the whole value. With a stable sort, if you sort by name first and then by score, the names stay in order within each score. With an unstable sort, sorting by score may not keep the names in order within each score. When the original order of equal keys matters, you need stability.

How to Achieve Stability

Stability is not just a property of an algorithm. It can be built in through design. There are two main strategies.

• Strategy 1: Use a stable algorithm. The simplest approach: choose an implementation that is inherently stable (Merge sort, Timsort, Powersort). No extra effort needed.
• Strategy 2: Break ties by original position. Before sorting, record each element’s original position, then compare by key first and, if the keys are equal, by original position. Since no two elements then tie, the original order is preserved. This does not rely on the algorithm being stable, but recording the positions takes extra memory proportional to the number of elements.

C#’s OrderBy / ThenBy are a clear example of strategy 2. C#’s Array.Sort is an unstable sort, but OrderBy / ThenBy build an array of keys and an array of original positions, and compare equal keys by original position, which guarantees stability.

Choose a Sort by Extra Memory and Stability

Does it keep the order of equal keys? Does it sort within the original array? Together, the answers divide the implementation variants into four groups.

Block sort (WikiSort) is stable and in-place, has O(n log n) worst-case time, and uses O(1) extra memory. Timsort is stable but not in-place and uses O(n) extra memory.

To see the strategy in each language: Standard Sorts Across Languages

How algorithms are built

Many fast sorts split the array into small parts, sort them, and combine the results into the whole. The split can be top-down, dividing the whole recursively, or bottom-up, building up from small units. The flow also changes between merge-based designs, which settle the order when combining, and partition-based designs, which settle it when splitting.

Same complexity, different speeds

Quicksort, merge sort, and heapsort all have an average complexity of O(n log n). Even so, they do not finish in the same time. Complexity describes how the cost grows; it does not show how long one operation takes or differences by a constant factor.

Two sorts with the same average O(n log n) can still run at different speeds. Complexity describes how the work grows as the input grows; it does not say how many comparisons, reads, and writes each element costs.

Fewer Calls and Copies

The same algorithm can run faster depending on how it is put together. Some techniques replace recursion with a loop to make fewer function calls; others cut down the reads and writes to a buffer.

Ways to cut calls and copies

Example: the optimization that turns recursion into a loop

Pruning and Early Termination

An input may already contain sections that are in order. If a sort can find such a section, it can skip sorting it again. Checking whether a section is in order also takes comparisons, so implementations keep the check cheap and stop it as soon as it looks unpromising.

Ways to skip work

Example: stopping a partial insertion sort early

Pattern Adaptation and Strategy Switching

Real data can contain ascending or descending stretches, or many repeated values. When a sort finds such a feature, switching to a method that suits it reduces comparisons and moves. Some techniques also switch to another method as soon as the input turns out to be a poor fit for the current one. Switching is a way of building a sort, separate from the property “adaptive”: a sort that switches methods but does not finish in nearly linear time when only a few elements are out of place (pdqsort, for example) is not called adaptive.

Ways to match the input

Example: Timsort reusing ordered runs

Fewer Hard-to-Predict Branches

Fewer comparisons do not always produce a shorter running time. A CPU also waits on unpredictable branches and distant memory accesses, so two implementations of the same algorithm can run at different speeds.

A CPU keeps recently used data in a fast cache, predicts which way each conditional branch will go, and overlaps instructions that do not wait for one another. So it stalls when a branch prediction is wrong, when an instruction needs the result of the one before it, and when data is not in the cache. Changing how branches are written, how instructions are ordered, and where data is kept reduces this waiting.

When irregular conditional branches follow one another, the CPU has trouble predicting where to go next and waits each time a prediction is wrong. Removing branches also removes those failed predictions. Using the result of a comparison in a calculation instead of a jump, so that the branch disappears, is called branchless code.

Ways to remove branches

Example: a partition written with a branch and a branchless partition

if (value < 33) put it on the left;
else put it on the right;

Letting the CPU Overlap Instructions

Even within a single core, a CPU works on several instructions at once when they do not use each other’s results. When each instruction needs the result of the one before it, though, the CPU can only run them one at a time. Placing pieces of work that do not use each other’s results side by side lets the CPU overlap them. Running instructions that do not use each other’s results at the same time is called instruction-level parallelism (ILP).

Ways to make work independent

Example: a front-to-back merge and a bidirectional merge

Keeping Data Small and Reading It in Order

When a CPU reads data from memory, it brings nearby data into the cache along with it. Reading neighbouring locations one after another uses all of that data. Keeping the working data small makes it more likely to fit in the cache. Block partitioning also reads elements a block at a time, which helps here too.

Ways to arrange and read data

Example: reading in order and keeping values small

Comparing Several Values with One Instruction

SIMD (Single Instruction, Multiple Data) is a CPU feature that applies one instruction to several values at once. A 128-bit register holds four 4-byte values (such as int). Comparing two such registers performs four comparisons with one instruction. Because SIMD runs inside one core and mixes with ordinary instructions, an algorithm can use it for just one part, such as the comparisons in a partition or the sorting of a small range. It works when the keys have a fixed size and the CPU can compare them directly, such as integers and floating-point numbers.

Sorting with SIMD

Example: comparing one pair at a time versus four pairs at once

Sharing the Work Across Cores or a GPU

Besides techniques inside a single core, the work of sorting can be divided across several CPU cores or a GPU and run at the same time. This is called parallelism.

It does not speed up every input, though. Handing out the work and waiting for it to finish take time, so a small input can even get slower. Parallelism pays off on large inputs, where the time saved by sharing the work exceeds that cost.

CPU cores and GPUs

Example: sorting with one core and with four cores

Comparing and Classifying Sorts

When thinking about how sorts differ, it helps to look separately at what decides the order, how the sort proceeds, how much extra memory it uses, and which properties hold. Two comparison sorts, for example, can still differ in how they use extra memory and in whether they keep elements with equal keys in their original order.

Example: comparing Introsort and Timsort

Introsort and Timsort are both comparison sorts. Are they the same in the other aspects as well?

What they share is that comparisons decide the order and that both finish in O(n log n) in the worst case. They differ in how they sort, in extra memory, in stability, and in how they handle ordered input. The name “comparison sort” alone does not show these differences.

Classifying sorts

A sort has several features at once: how it sorts, how much extra memory it uses, its properties, and more. So rather than placing a sort in a single class, recent approaches give it several classifications.

The classic classification

Donald Knuth, sometimes called the “father of the analysis of algorithms”, is a computer scientist who received the Turing Award in 1974. The Art of Computer Programming, which he has been writing since 1968, is a series of books that sets out the central algorithms of programming systematically, together with their mathematical analysis.

Its third volume, Sorting and Searching, divides internal sorting, which sorts data that fits in memory, into five kinds: insertion, exchanging, selection, merging, and distribution. Under this scheme, quicksort is an exchange sort and heapsort is a selection sort. These names are still common in books and papers, but a modern practical sort that combines several methods may not fit any single one.

Reference: Donald E. Knuth, The Art of Computer Programming, Volume 3, Section 5.2.

Classification today

Recent textbooks and curricula do not settle a sort into a single class. They classify it along several aspects at once.

A single sort belongs to several of these classes at once. Timsort, for example, is a comparison sort, is stable, and is adaptive. CS2023 also lists Timsort alongside quicksort and merge sort as an example of an O(n log n) sort.

References: Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed., Chapter 8; ACM/IEEE-CS/AAAI, CS2023 Body of Knowledge, Algorithmic Foundations (AL). CS2023 Body of Knowledge

SortVivo’s categories

To make algorithms easier to find, SortVivo gives each algorithm one category. Seven of its ten categories are ways of sorting: the five classic kinds plus partition and heap. Quicksort, an exchange sort in the classic scheme, is PARTITION here, and heapsort, a selection sort there, is HEAP. Algorithms that do not fit a way of sorting are grouped by structure or as other. A sort that combines several methods goes in the category of its main method, and the other methods it uses are listed in its description under “Combined with”: introsort is PARTITION, and Timsort is MERGE. Properties such as being stable or adaptive are not categories; you find them with the filters.

Modern Standard Sorts and How They Change

Why do standard sorts get replaced? In 2022, Go moved the sort that does not promise to preserve equal-key order to pdqsort. In 2024, Rust replaced both its stable sort, which preserves that order, and its unstable sort, which does not promise to preserve it. Each language weighs API needs, speed, memory, and robustness differently.

What matters when choosing a standard sort?

A faster implementation does not automatically become the standard sort. Besides speed, a standard sort is chosen by these conditions.

What is adaptivity?

An input may already contain ordered stretches or many duplicate keys. A sort can use those features to reduce comparisons and movement.

Adaptivity means using order already present in the input to do less work. An adaptive sort finishes in linear time on sorted input, and in nearly linear time when only a few elements are out of place. Grouping duplicate values changes the processing to suit repeated values rather than order, so it is treated separately from adaptivity. API guarantees, memory, and portability are decided separately as well.

Stable and unstable sorts sit behind separate APIs so that callers can choose between different guarantees and costs.

Standard Sorts Across Languages

Languages are listed alphabetically. The badge beside each language shows its stability guarantee. Select a language for its API and implementation details, or an algorithm for an explanation of how it works.

As of 2026-03. API details come from official specifications and documentation. Implementation details come from released source code and release notes. Internal implementations may change.

APIs, implementations, and reasons by language

Languages weigh API guarantees, compatibility, speed, and memory differently. “Stable” promises to preserve equal-key order; “No guarantee” means callers cannot rely on that order. “Not applicable” marks primitive arrays whose equal values cannot be distinguished. Sources appear at the end of each card.

Notable Algorithms

pdqsort, Powersort, ipnsort, and driftsort are implementations or techniques adopted by standard sorts since 2017. They reduce work by using input structure and CPU behavior while preserving the required stability and worst-case bounds.

Unstable sorts: faster quicksort with a worst-case bound

Stable sorts: merge sort with better merging, helped by quicksort

Notable techniques

Pivot selection, the sorting of short ranges, and merge order all affect overall performance. Different sorts can benefit from the same technique.