Sort Basics

Before You Call a Sorting API

We have seen sorting as putting elements into an order that fits a purpose. Now let us look at what to decide before calling a sorting API in application code.

Before choosing an algorithm name, check the result the application needs and the contract of the API. Decide these six items in order to tell whether a standard full sort fits or another tool is the better match.

1. 1

   Do you need a complete order of every item?

   If the result does not need to decide which of every pair of elements comes first, a full sort can be unnecessary work. Look first for the API or data structure that directly matches the result.

   • 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

   Does the key or comparator define a consistent order?

   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 changes the input also changes the order that code sees. Check the signature and documentation to learn whether the input changes or the API returns a new sequence.

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. Read that guarantee from the API instead of inferring it from an algorithm name.

5. 5

   Are memory, comparisons, or key extraction constrained?

   Check not only whether a temporary array fits, but also whether text ordering or key calculation is expensive. An expensive key can be better extracted and stored once instead of recomputed on every comparison.

6. 6

   Are you relying on an API guarantee or today's implementation?

   Correctness properties such as stability, worst-case complexity, and mutation must come from the API contract. An internal implementation such as pdqsort or ipnsort can explain performance, but it is not necessarily a promise that survives future versions.

See the error-prone boundary in code

Which API keeps the input unchanged? Compare JavaScript's `sort` and `toSorted`.

const ordered = items.toSorted(compare);
items.sort(compare);

toSorted returns a new array, while sort rearranges items itself. Looking only at the returned value hides this difference.

What does a sorting API promise?

When choosing a sorting API, check these four parts of its contract. Some APIs leave the order of equal keys unspecified. Others, including APIs named stable_sort, explicitly promise to preserve that order.

Order

A key or comparator defines which item comes first.

Same elements

Nothing is lost or invented; only the order changes.

Equal keys

Stability says whether items with equal keys keep their original relative order.

Result shape

Some APIs mutate the input, while others return a new ordered sequence. One language often has both, as with sort and toSorted in JavaScript or list.sort() and sorted() in Python.

What a comparator must guarantee

Some languages let callers supply the ordering. A key function extracts a value, as in Python's sorted(key=...) or C#'s OrderBy(x => x.Score). A comparator receives two elements and reports which comes first. JavaScript's sort accepts a comparator.

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

The language also decides what happens when you pass nothing. JavaScript's Array.prototype.sort converts elements to strings before ordering them when the comparator is omitted, so [1, 2, 10] comes back as [1, 10, 2]. For when you want numeric order, the language lets you pass a comparator.

[1, 2, 10].sort();
[1, 2, 10].sort((a, b) => a - b);

A comparator must give a consistent answer about which element comes first. Check these three rules.

Consistent

Comparing the same two items always gives the same answer. No randomness, no clock, no state that changes while the sort is running. Swapping the arguments has to agree too: it must never report that a precedes b and that b precedes a.

Transitive

If a comes before b and b comes before c, then a comes before c. Floating point error and rounded scores are common ways this breaks.

Ties stay consistent

Two items where neither precedes the other are tied. If a ties b and b ties c, then a must tie c. Comparing with a tolerance (equal when the difference is below a threshold) is the classic way to break this.

A wrong comparator does not only fail to put things in order; it can raise an exception. Java's Arrays.sort and Collections.sort, for example, throw IllegalArgumentException (Comparison method violates its general contract!) when they detect a violation.

Most languages ship a sorting algorithm in their standard library. What stays on the calling side is which key to order by, and whether the comparator you hand over holds to the three rules above.

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 Θ(n · d) for d digits. 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, a sort can reduce comparisons and movement by using order already present in the input. Adaptive sorts use this idea.

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 moves elements within the original array instead of allocating a temporary array proportional to the input size. It usually needs O(1) working storage, although some implementations use about O(log n) memory to record recursive calls. A sort with a temporary array may need O(n) extra memory.

On embedded devices or in memory-constrained environments, allocating O(n) extra memory is often impractical. In such cases, in-place sorts become a strong choice.

Stability

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

This is what pays off when you want to order by two keys. Sort by name first, then sort by score with a stable sort, and within each score the names stay in order. Stacking stable sorts is enough to build a multi-level ordering. An unstable sort loses the first pass, so the two keys have to be handled together inside the comparator instead.

Compare Implementation Variants with Two Questions

Does it keep the order of equal keys? Does it sort without extra memory? Those two answers split the implementation variants into four groups. The amount of extra memory varies by implementation.

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.

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: Embed the original position in the comparator. Layer stability on top of an unstable sort. Design the comparator as follows: compare by key first; if the keys are equal, compare by original position. This imposes a total order so the algorithm never sees tied keys. Stability is guaranteed by the comparison specification, not the algorithm.

.NET's OrderBy / ThenBy follow strategy 2. Rather than using a stable sort, .NET embeds the original position into the comparison function so the order is fully decided. The sort inside can change, and stability still holds as an API promise.

To see which of these two strategies your own language takes: Standard Sorts Across Languages

How algorithms are built

A sort is built from choices about how to divide a problem and combine the results. Top-down and bottom-up processing, and merge-based and partition-based designs, follow different flows.

Why implementation changes speed

Algorithms with the same average O(n log n) complexity can run at different speeds. Recursion means that a function calls itself on a smaller problem. A buffer is temporary storage for values used during processing. Changing recursion, buffers, and copying can reduce calls and memory use.

QuickSort and HeapSort both average O(n log n). Given the same random input, which one finishes first? The Sortube race scales each lane by its measured time, so the lane that reaches the end first is the one that actually ran faster. Make your prediction, then compare the two measured times. The result holds for this input, this implementation, and this machine.

Open the QuickSort vs HeapSort race in Sortube

Adapting to the Input

Pruning and Early Termination

Find processing that is not needed and skip it.

Pattern Adaptation and Strategy Switching

Techniques that detect structure in the input and choose a strategy accordingly.

Low-Level Optimization

A CPU keeps recently used data in fast caches, predicts which way a branch will go, and overlaps instructions that do not depend on one another. Low-level optimization arranges work to use these caches, predictions, and instruction pipelines well.

Limited but Practical Techniques

Parallelism divides work across CPU cores or a GPU. SIMD applies one instruction to several values at once. Both work best on large inputs or keys the CPU can compare directly.

Six ways to compare sorts

Compare a sort by the information it uses, how it makes progress, its design strategy, data and execution structure, guaranteed properties, and implementation techniques. These views reveal differences that one label cannot.

Merge and partition are divide-and-conquer examples. Insertion and selection are decrease-and-conquer examples. A heap is a transform-and-conquer example. Recursion versus iteration is a separate choice.

Compare QuickSort and Timsort

QuickSort and Timsort are both comparison sorts. Are they alike in other ways? Compare them across the six dimensions.

They share only one point: both use comparisons to decide order. Their progress, strategy, memory use, and guarantees differ. The label "comparison sort" does not show those differences.

Reading SortVivo's categories

Sorts can be classified by how they make progress, the data they use, or the properties they guarantee.

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 new implementation may not be better in every way. Standard sorts balance these needs.

• API contract and compatibility Whether it preserves stability, avoids a breaking change, retains observable equal-key order, and respects behavior existing code depends on.
• Worst case and robustness Whether complexity stays bounded on skewed or deliberately constructed inputs and has a predictable limit. This also matters for denial-of-service resistance when an attacker controls the input.
• Real workloads Whether it saves work on ordered stretches already present in the input (runs), duplicate keys, skew, or elements that are expensive to compare in that language.
• Memory and code size Whether temporary storage, records of recursive calls, and executable size added when generic code is specialized for each type fit the target environment.
• CPU and specialization Whether it benefits from caches, branches, data movement, fast paths for keys stored in a fixed number of bits such as integers, and types or comparisons known at compile time.
• Portability and maintenance Whether it works across targets, is tractable to verify, and remains maintainable at standard-library scale.

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 detecting features of the input and changing the processing. A sort may reuse ordered runs or group duplicate values. API guarantees, memory, and portability are decided separately.

Stable and unstable sorts sit behind separate APIs for a different reason: they let callers choose between different guarantees and costs.

Notable Algorithms

Recent sorts each solve a different problem. Read them by the problem each one set out to solve.

Standard Sorts Across Languages

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.

Why Each Language Chose This Sort

Languages give different priority to API guarantees, compatibility, speed, and memory.

C

C standardizes a portable qsort() interface and leaves the implementation to each platform. It does not specify the internal algorithm or the order of equal values. Official documentation

C++

C++ specifies complexity and results, then leaves the concrete algorithm to each implementation. Implementations can change while preserving the API contract. Official documentation (sort) Official documentation (stable_sort)

C++ (Boost)

Boost.Sort exposes APIs named after concrete algorithms. Callers can select an implementation from properties such as stability and resistance to difficult inputs. Implementation source

Rust

Rust 1.81 changed sorting to improve standard-library speed and quality. Its release notes report substantial gains for sorting and partial selection, which finds only the elements at needed ranks. Release notes Official documentation

Go

Go's unstable path keeps O(n log n) even on skewed inputs. Its stable path uses SymMerge to limit extra memory while remaining straightforward to verify. Implementation source Implementation notes

Zig

Zig added a faster API for callers that do not need stability while preserving the existing stable, in-place guarantee. Separate APIs let callers choose between guarantees and speed. Release notes Design discussion #15388 Design discussion #11117

Java (primitives)

Primitive arrays do not distinguish equal values, so Java can prioritize speed over stability. Its documentation describes Dual-Pivot Quicksort as generally faster than the older one-pivot form. Official documentation

Java (objects)

Java guarantees stability for object arrays. TimSort fits that contract and can reduce comparisons on partially ordered input. Official documentation

.NET / C#

Some code depends on the deterministic order of equal values produced by .NET Array.Sort(). Changing to another unstable implementation can therefore break compatibility. Design discussion Code change

Python

Python 3.11 kept stability and adaptivity but changed the merge order to PowerSort's policy. The goal was fewer comparisons. Implementation notes Design discussion

JavaScript

ECMAScript specifies observable results and leaves the algorithm to each engine. When ES2019 required stability, engines such as V8 moved to stable implementations. Official documentation Implementation notes

Swift

Swift turned the already stable behavior of sort() into a documented API guarantee. Callers can now rely on the order of equal keys. Specification proposal SE-0372 Developer discussion

Kotlin

Kotlin keeps one stability guarantee while delegating implementation to JVM, JavaScript, and Native. This reuses each platform's standard facilities. Official documentation

Dart

Dart's List.sort() does not guarantee stability and uses an in-place Dual-Pivot Quicksort. Callers that need stability use a different API. Implementation source

PHP 8+

PHP 8.0 kept its existing sort and broke ties by original position. This added stability with a small implementation change. Change proposal

Ruby

Ruby uses an operating-system sort function when available and a built-in implementation otherwise. Portability takes priority over one uniform algorithm. Implementation source