Sorting: stability, in-place and adaptivity

Sorting puts items in order by a key, and three properties tell sorts apart beyond their speed. A stable sort keeps items with equal keys in the order they arrived. An in-place sort rearranges the items inside the storage they already occupy, with only a little extra memory for bookkeeping. An adaptive sort does less work when its input is already partly in order. Stability is what lets you sort by several keys one key at a time, in-place sorting matters when memory is tight, and adaptivity pays off because real data often arrives nearly sorted. This lesson defines each property, measures it in runs of Python, JavaScript, Java, C++ and Go, and lists which standard-library sorts promise stability.

Three properties of a sort

NIST’s Dictionary of Algorithms and Data Structures defines all three, and they are independent of each other:

• Stable. Items with equal keys come out in the same relative order they went in. Sort a register that is in roll-number order by marks, and a stable sort leaves every group of equal marks in roll-number order.
• In place. The sorted items end up in the storage the input occupied. The algorithm may keep a sublinear amount of bookkeeping, such as the index ranges quicksort still has to process, but only a constant number of items outside the array at any moment.
• Adaptive. The cost falls as the disorder of the input falls. On input that is already sorted, insertion sort makes n − 1 comparisons instead of about n²/2.

Stability only matters when equal keys can be told apart. Sorting plain integers, a stable and an unstable sort give the same result; sorting records by one field, they may not.

The sorts of this module, property by property:

• Selection sort: not stable, because a swap can jump an item over its equals; in place; not adaptive.
• Bubble sort with an early exit: stable, in place and adaptive.
• Insertion sort: stable, in place and adaptive.
• Merge sort on an array: stable when ties take the left item; not in place, since it needs a buffer of n items; adaptive only if it looks for sorted runs.
• Quicksort: not stable; in place, with a stack of O(log n) ranges; not adaptive.
• Python’s list.sort(): stable, mostly in place, with a buffer of up to n/2 pointers, and adaptive.

The later lessons of this module build each of these sorts and prove every line of this list.

Stable passes sort by several keys

A results list must show the highest marks first and, among equal marks, the smallest roll number first. There are two ways to get that order. One sort with a key tuple compares marks first and roll numbers only on a tie. Two stable sorts do the same job one key at a time, the secondary key first:

"""Exam results ordered by marks, highest first, then by roll number: one sort with a key tuple, or two stable sorts."""
from collections import namedtuple

Result = namedtuple("Result", "roll name marks")

results = [
    Result(14, "Ana", 82),
    Result(3, "Kabir", 91),
    Result(27, "Lena", 82),
    Result(8, "Omar", 76),
    Result(21, "Zoya", 91),
    Result(5, "Neel", 82),
]

# One sort: the key tuple puts higher marks first (negated) and breaks ties by roll number.
one_key = sorted(results, key=lambda r: (-r.marks, r.roll))

# Two stable sorts: the secondary key (roll number) first, then the primary key (marks).
by_roll = sorted(results, key=lambda r: r.roll)
two_passes = sorted(by_roll, key=lambda r: r.marks, reverse=True)

for r in two_passes:
    print(f"{r.marks:>3}  roll {r.roll:>2}  {r.name}")
print("same order both ways:", one_key == two_passes)

# The passes in the wrong order: the last sort wins, so this is ordered by roll number.
wrong = sorted(sorted(results, key=lambda r: r.marks, reverse=True), key=lambda r: r.roll)
print("marks first, then roll:", [r.roll for r in wrong])

# Sorting up and then reversing the list also reverses the order of equal marks.
flipped = sorted(by_roll, key=lambda r: r.marks)[::-1]
print("sorted up, then reversed:", [r.roll for r in flipped])

 91  roll  3  Kabir
 91  roll 21  Zoya
 82  roll  5  Neel
 82  roll 14  Ana
 82  roll 27  Lena
 76  roll  8  Omar
same order both ways: True
marks first, then roll: [3, 5, 8, 14, 21, 27]
sorted up, then reversed: [21, 3, 27, 14, 5, 8]

Both ways give the same order. The second pass reorders the list by marks only, and because it is stable, the three students with 82 marks keep the order that the first pass gave them: roll numbers 5, 14 and 27.

The order of the passes is the whole trick. The last sort decides the main order, and an earlier sort survives only inside the ties of the sorts that follow it, so the least important key goes first. Run the passes the other way round and the result is simply in roll-number order, as the line starting “marks first” shows.

A direction can change from pass to pass. Python’s documentation states that reverse=True keeps a sort stable, so pass 2 could list the highest marks first without disturbing the roll numbers. Sorting upwards and then reversing the list is not the same: the reversal also turns every group of equal marks around, which put roll 27 before 14 and 5 in the last line.

Use a key tuple when every key is a number or can be negated; it is a single sort. Use stable passes when a key cannot be negated, such as names in descending order, or when the keys are chosen at run time, as when a user clicks column headers one after another.

A stability probe in five languages

A promise of stability is the only thing to rely on, but a probe shows what an unstable sort really does. This one builds 2,000 records with only 7 distinct keys, from the same seeded generator in every language, sorts them by key and counts the order breaks: neighbours with equal keys whose input positions are out of order. A stable sort has none.

"""A stability probe: sort 2,000 records that share 7 keys and count the equal keys that left their input order."""


def make_records(n=2000, seed=12345):
    """(key, input position) pairs; the key comes from a small seeded generator, so every language gets the same data."""
    x = seed
    records = []
    for position in range(n):
        x = x * 48271 % 2147483647
        records.append((x % 7, position))
    return records


def order_breaks(records):
    """Neighbours with equal keys whose input positions are out of order (0 for every stable sort)."""
    return sum(1 for a, b in zip(records, records[1:]) if a[0] == b[0] and a[1] > b[1])


def selection_sort_by_key(records):
    """Selection sort that compares keys only and swaps the smallest key to the front."""
    a = list(records)
    for i in range(len(a) - 1):
        smallest = i
        for j in range(i + 1, len(a)):
            if a[j][0] < a[smallest][0]:
                smallest = j
        a[i], a[smallest] = a[smallest], a[i]
    return a


records = make_records()
print(f"{len(records)} records, {len({k for k, _ in records})} distinct keys")

in_place = list(records)
in_place.sort(key=lambda r: r[0])
for name, result in [
    ("sorted(key=...)", sorted(records, key=lambda r: r[0])),
    ("list.sort(key=...)", in_place),
    ("selection sort", selection_sort_by_key(records)),
]:
    breaks = order_breaks(result)
    print(f"{name:<20}{breaks:>5} order breaks  {'stable here' if breaks == 0 else 'NOT stable'}")

2000 records, 7 distinct keys
sorted(key=...)         0 order breaks  stable here
list.sort(key=...)      0 order breaks  stable here
selection sort        570 order breaks  NOT stable

// A stability probe: sort 2,000 records that share 7 keys and count the equal keys that left their input order.

function makeRecords(n = 2000, seed = 12345) {
  // (key, input position) pairs from the same seeded generator as the Python version.
  let x = seed;
  const records = [];
  for (let position = 0; position < n; position++) {
    x = (x * 48271) % 2147483647;
    records.push({ key: x % 7, position });
  }
  return records;
}

function orderBreaks(records) {
  // Neighbours with equal keys whose input positions are out of order (0 for every stable sort).
  let breaks = 0;
  for (let i = 1; i < records.length; i++) {
    if (records[i - 1].key === records[i].key && records[i - 1].position > records[i].position) breaks++;
  }
  return breaks;
}

function selectionSortByKey(records) {
  // Selection sort that compares keys only and swaps the smallest key to the front.
  const a = records.slice();
  for (let i = 0; i < a.length - 1; i++) {
    let smallest = i;
    for (let j = i + 1; j < a.length; j++) if (a[j].key < a[smallest].key) smallest = j;
    [a[i], a[smallest]] = [a[smallest], a[i]];
  }
  return a;
}

const records = makeRecords();
console.log(`${records.length} records, ${new Set(records.map((r) => r.key)).size} distinct keys`);

const byKey = (a, b) => a.key - b.key;
for (const [name, result] of [
  ['toSorted(byKey)', records.toSorted(byKey)],
  ['sort(byKey)', records.slice().sort(byKey)],
  ['selection sort', selectionSortByKey(records)],
]) {
  const breaks = orderBreaks(result);
  console.log(`${name.padEnd(20)}${String(breaks).padStart(5)} order breaks  ${breaks === 0 ? 'stable here' : 'NOT stable'}`);
}

2000 records, 7 distinct keys
toSorted(byKey)         0 order breaks  stable here
sort(byKey)             0 order breaks  stable here
selection sort        570 order breaks  NOT stable

Python’s two sorts and JavaScript’s two sorts kept every group in input order. The selection sort, written for this probe, did not: each swap that brings the smallest key to the front can throw the item it replaces past its equals. The same records in Java, C++ and Go:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

// The stability probe in Java: the same 2,000 records, sorted by key with List.sort and Arrays.sort.
public class StabilityProbe {
    record Rec(int key, int position) {}

    static List<Rec> makeRecords(int n, long seed) {
        long x = seed;
        List<Rec> records = new ArrayList<>();
        for (int position = 0; position < n; position++) {
            x = x * 48271 % 2147483647;
            records.add(new Rec((int) (x % 7), position));
        }
        return records;
    }

    static int orderBreaks(List<Rec> r) {
        int breaks = 0;
        for (int i = 1; i < r.size(); i++) {
            if (r.get(i - 1).key() == r.get(i).key() && r.get(i - 1).position() > r.get(i).position()) breaks++;
        }
        return breaks;
    }

    static void report(String name, int breaks) {
        System.out.printf("%-24s%5d order breaks  %s%n", name, breaks, breaks == 0 ? "stable here" : "NOT stable");
    }

    public static void main(String[] args) {
        List<Rec> records = makeRecords(2000, 12345);
        Comparator<Rec> byKey = Comparator.comparingInt(Rec::key);

        List<Rec> list = new ArrayList<>(records);
        list.sort(byKey);
        report("List.sort", orderBreaks(list));

        Rec[] array = records.toArray(new Rec[0]);
        Arrays.sort(array, byKey);
        report("Arrays.sort(Rec[])", orderBreaks(Arrays.asList(array)));
    }
}

// The stability probe in C++: the same 2,000 records, sorted by key with std::sort and std::stable_sort.
#include <algorithm>
#include <cstdio>
#include <vector>

struct Rec {
    int key;
    int position;
};

std::vector<Rec> make_records(int n, long long seed) {
    long long x = seed;
    std::vector<Rec> records;
    for (int position = 0; position < n; ++position) {
        x = x * 48271 % 2147483647;
        records.push_back({static_cast<int>(x % 7), position});
    }
    return records;
}

int order_breaks(const std::vector<Rec>& r) {
    int breaks = 0;
    for (std::size_t i = 1; i < r.size(); ++i) {
        if (r[i - 1].key == r[i].key && r[i - 1].position > r[i].position) ++breaks;
    }
    return breaks;
}

void report(const char* name, int breaks) {
    std::printf("%-24s%5d order breaks  %s\n", name, breaks, breaks == 0 ? "stable here" : "NOT stable");
}

int main() {
    const std::vector<Rec> records = make_records(2000, 12345);
    auto by_key = [](const Rec& a, const Rec& b) { return a.key < b.key; };

    std::vector<Rec> a = records;
    std::sort(a.begin(), a.end(), by_key);
    report("std::sort", order_breaks(a));

    std::vector<Rec> b = records;
    std::stable_sort(b.begin(), b.end(), by_key);
    report("std::stable_sort", order_breaks(b));
}

// The stability probe in Go: the same 2,000 records, sorted by key with the sort and slices packages.
package main

import (
	"cmp"
	"fmt"
	"slices"
	"sort"
)

type rec struct{ key, position int }

func makeRecords(n int, seed int64) []rec {
	x := seed
	records := make([]rec, 0, n)
	for position := 0; position < n; position++ {
		x = x * 48271 % 2147483647
		records = append(records, rec{int(x % 7), position})
	}
	return records
}

func orderBreaks(r []rec) int {
	breaks := 0
	for i := 1; i < len(r); i++ {
		if r[i-1].key == r[i].key && r[i-1].position > r[i].position {
			breaks++
		}
	}
	return breaks
}

func report(name string, breaks int) {
	verdict := "NOT stable"
	if breaks == 0 {
		verdict = "stable here"
	}
	fmt.Printf("%-24s%5d order breaks  %s\n", name, breaks, verdict)
}

func main() {
	records := makeRecords(2000, 12345)
	byKey := func(a, b rec) int { return cmp.Compare(a.key, b.key) }

	a := slices.Clone(records)
	slices.SortFunc(a, byKey)
	report("slices.SortFunc", orderBreaks(a))

	b := slices.Clone(records)
	slices.SortStableFunc(b, byKey)
	report("slices.SortStableFunc", orderBreaks(b))

	c := slices.Clone(records)
	sort.Slice(c, func(i, j int) bool { return c[i].key < c[j].key })
	report("sort.Slice", orderBreaks(c))

	d := slices.Clone(records)
	sort.SliceStable(d, func(i, j int) bool { return d[i].key < d[j].key })
	report("sort.SliceStable", orderBreaks(d))
}

from terminal import session, show_versions

# StabilityProbe.java runs as a single source file; the C++ probe is built with optimisation and warnings on.
show_versions("java -version", "clang++ --version", "go version")
session("""
java StabilityProbe.java
clang++ -std=c++23 -O2 -Wall -Wextra stability_probe.cpp -o stability_probe && ./stability_probe
go run stability_probe.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java StabilityProbe.java
List.sort                   0 order breaks  stable here
Arrays.sort(Rec[])          0 order breaks  stable here
$ clang++ -std=c++23 -O2 -Wall -Wextra stability_probe.cpp -o stability_probe && ./stability_probe
std::sort                 987 order breaks  NOT stable
std::stable_sort            0 order breaks  stable here
$ go run stability_probe.go
slices.SortFunc          1001 order breaks  NOT stable
slices.SortStableFunc       0 order breaks  stable here
sort.Slice               1001 order breaks  NOT stable
sort.SliceStable            0 order breaks  stable here

std::sort broke the order 987 times and Go’s slices.SortFunc and sort.Slice 1,001 times each, while std::stable_sort, slices.SortStableFunc, sort.SliceStable and both Java sorts broke it never. What the libraries promise:

• Python: list.sort() and sorted() are stable.
• JavaScript: Array.prototype.sort and toSorted are stable.
• Java: List.sort and Arrays.sort for object arrays are stable. Arrays.sort for primitive arrays is not, but there equal values cannot be told apart.
• C++: std::stable_sort is stable; std::sort is not guaranteed to be.
• Go: slices.SortStableFunc, sort.Stable and sort.SliceStable are stable; slices.SortFunc, sort.Sort and sort.Slice are not guaranteed to be.

JavaScript’s guarantee is in the ECMAScript specification itself, which requires items that compare equal to keep their order. Java documents a stable, adaptive, iterative merge sort for objects and a dual-pivot quicksort for primitive arrays. A probe with zero breaks proves nothing about a sort without the promise: an unstable sort can keep the order of a short or lucky input, which is why the probe uses many records with many repeats.

JavaScript sorts strings unless told otherwise

Without a comparator, JavaScript’s sort turns every item into a string and compares the strings code unit by code unit, so numbers are not sorted by value:

// JavaScript's sort without a comparator compares the items as strings, code unit by code unit.
const show = (label, items) => console.log(`${label.padEnd(34)}[${items.map(String).join(', ')}]`);

show('[10, 9, 1].sort()', [10, 9, 1].sort());
show('[10, 9, 1].sort((a, b) => a - b)', [10, 9, 1].sort((a, b) => a - b));
show('[5, 25, 100].sort()', [5, 25, 100].sort());
show("['b', 'C', 'a'].sort()", ['b', 'C', 'a'].sort());
show('[3, undefined, 1].sort()', [3, undefined, 1].sort());

[10, 9, 1].sort()                 [1, 10, 9]
[10, 9, 1].sort((a, b) => a - b)  [1, 9, 10]
[5, 25, 100].sort()               [100, 25, 5]
['b', 'C', 'a'].sort()            [C, a, b]
[3, undefined, 1].sort()          [1, 3, undefined]

[10, 9, 1] becomes [1, 10, 9] because the string “10” comes before “9”. Capital letters come before lower-case ones, since their code units are smaller, and undefined always goes last, as the specification requires. The comparator (a, b) => a - b sorts numbers by value; its result must be a number, negative when a goes first.

In place, measured

Python’s list.sort() sorts the list’s own storage and returns None, while sorted() builds a new list. Neither avoids extra memory, as this run shows. It measures the peak memory each one allocates, in pointer-sized slots (8 bytes each on a 64-bit build):

"""Peak extra memory of list.sort() and sorted() on 100,000 integers, counted in pointer-sized slots."""
import random
import struct
import tracemalloc

SLOT = struct.calcsize("P")  # bytes in one pointer: 8 on 64-bit builds


def extra_slots(work, values):
    """Peak memory allocated while work(values) runs, in pointer-sized slots."""
    tracemalloc.start()
    before = tracemalloc.get_traced_memory()[0]
    work(values)
    peak = tracemalloc.get_traced_memory()[1]
    tracemalloc.stop()
    return (peak - before) // SLOT


n = 100_000
shuffled = list(range(n))
random.Random(1).shuffle(shuffled)

for name, values in [("already sorted", list(range(n))), ("shuffled", shuffled)]:
    in_place = extra_slots(lambda v: v.sort(), values[:])
    copy = extra_slots(sorted, values[:])
    print(f"{name:<15} list.sort(): {in_place:>7,} slots   sorted(): {copy:>7,} slots")

already sorted  list.sort():       0 slots   sorted(): 100,000 slots
shuffled        list.sort():  49,980 slots   sorted(): 149,980 slots

On sorted input list.sort() needed nothing: it found one run and stopped. On shuffled input it needed 49,980 slots, just under n/2, for the buffer its merges use. sorted() paid for a whole new list of 100,000 slots on top. So in Python, sorting in place means “no second list”, not “no extra memory”. C++’s std::stable_sort makes the same trade openly: it tries to allocate a buffer as large as the range and falls back to a slower algorithm, with O(n log² n) comparisons, when it cannot.

Adaptivity, counted

An adaptive sort’s cost depends on how much order the input already has. This run counts the comparisons Python’s sort makes on the same 10,000 numbers in four starting orders:

"""Counts the comparisons Python's sort makes on 10,000 items in four different starting orders."""
import math
import random


class Counted:
    """A number that counts every < comparison made between two Counted values."""

    __slots__ = ("value",)
    calls = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        Counted.calls += 1
        return self.value < other.value


def comparisons(values):
    items = [Counted(v) for v in values]
    Counted.calls = 0
    items.sort()
    assert [x.value for x in items] == sorted(values)
    return Counted.calls


n = 10_000
rng = random.Random(7)
ascending = list(range(n))
nearly = ascending[:]
for _ in range(10):  # ten neighbouring pairs swapped
    i = rng.randrange(n - 1)
    nearly[i], nearly[i + 1] = nearly[i + 1], nearly[i]
shuffled = ascending[:]
rng.shuffle(shuffled)

for name, values in [
    ("already sorted", ascending),
    ("sorted backwards", ascending[::-1]),
    ("sorted, 10 pairs swapped", nearly),
    ("shuffled", shuffled),
]:
    print(f"{name:<26}{comparisons(values):>9,} comparisons")
print(f"{'n log2 n for comparison':<26}{round(n * math.log2(n)):>9,}")

already sorted                9,999 comparisons
sorted backwards              9,999 comparisons
sorted, 10 pairs swapped     10,383 comparisons
shuffled                    120,163 comparisons
n log2 n for comparison     132,877

Sorted input took 9,999 comparisons, one per neighbouring pair. Reversed input took the same, because the sort recognises a descending run and reverses it in place. Ten swapped pairs cost only 384 comparisons more. Shuffled input took 120,163, close to log₂(10,000!) ≈ 118,458, the number of yes-or-no answers needed on average to tell all the possible orders apart. CPython’s design notes describe this sort as an adaptive, stable, natural merge sort: it finds the runs that are already in order and merges them.

Exercise and self-check

A booking office lists bookings by day, then by fare from highest to lowest, then by booking id. Write the order twice, once with a single key and once with one stable sort per rule:

def order_with_key(bookings):
    """The bookings by day (earliest first), then fare (highest first), then id (smallest first): one sort."""
    # Replace this line: sort once, with a key that encodes all three rules.
    return list(bookings)


def order_with_passes(bookings):
    """The same order, built with one stable sort per rule, each sort looking at a single field."""
    # Replace this line: sort by the least important rule first.
    return list(bookings)

import random

from bookings import order_with_key, order_with_passes

SAMPLE = [
    {"id": 7, "day": 2, "fare": 900},
    {"id": 3, "day": 1, "fare": 450},
    {"id": 9, "day": 2, "fare": 1400},
    {"id": 1, "day": 2, "fare": 900},
    {"id": 5, "day": 1, "fare": 450},
]
EXPECTED_IDS = [3, 5, 9, 1, 7]


def in_order(a, b):
    """True when booking a may come before booking b."""
    if a["day"] != b["day"]:
        return a["day"] < b["day"]
    if a["fare"] != b["fare"]:
        return a["fare"] > b["fare"]
    return a["id"] < b["id"]


def check(result, bookings):
    assert sorted(b["id"] for b in result) == sorted(b["id"] for b in bookings), "not a reordering of the input"
    for a, b in zip(result, result[1:]):
        assert in_order(a, b), f"{a} is placed before {b}"


def test_sample_with_key():
    """order_with_key orders the five sample bookings"""
    assert [b["id"] for b in order_with_key(SAMPLE)] == EXPECTED_IDS


def test_sample_with_passes():
    """order_with_passes orders the five sample bookings"""
    assert [b["id"] for b in order_with_passes(SAMPLE)] == EXPECTED_IDS


def test_input_unchanged():
    """both functions return a new list and leave the input as it was"""
    before = [dict(b) for b in SAMPLE]
    order_with_key(SAMPLE)
    order_with_passes(SAMPLE)
    assert SAMPLE == before


def test_random_lists():
    """on 200 random lists, both functions give a correct order"""
    rng = random.Random(11)
    for _ in range(200):
        ids = rng.sample(range(1, 1000), rng.randint(0, 30))
        bookings = [{"id": i, "day": rng.randint(0, 3), "fare": rng.choice([450, 900, 1250, 1400])} for i in ids]
        check(order_with_key(bookings), bookings)
        check(order_with_passes(bookings), bookings)

/** The bookings by day (earliest first), then fare (highest first), then id (smallest first): one sort. */
export function orderWithKey(bookings) {
  // Replace this line: sort once, with one comparator that encodes all three rules.
  return bookings.slice();
}

/** The same order, built with one stable sort per rule, each sort looking at a single field. */
export function orderWithPasses(bookings) {
  // Replace this line: sort by the least important rule first.
  return bookings.slice();
}

import { test, assert } from 'mysmartcopilot:test';
import { orderWithKey, orderWithPasses } from './bookings.mjs';

const SAMPLE = [
  { id: 7, day: 2, fare: 900 },
  { id: 3, day: 1, fare: 450 },
  { id: 9, day: 2, fare: 1400 },
  { id: 1, day: 2, fare: 900 },
  { id: 5, day: 1, fare: 450 },
];
const EXPECTED_IDS = [3, 5, 9, 1, 7];

function inOrder(a, b) {
  if (a.day !== b.day) return a.day < b.day;
  if (a.fare !== b.fare) return a.fare > b.fare;
  return a.id < b.id;
}

function check(result, bookings) {
  const ids = (list) => list.map((b) => b.id).sort((x, y) => x - y).join(',');
  assert.equal(ids(result), ids(bookings), 'not a reordering of the input');
  for (let i = 1; i < result.length; i++) {
    assert.ok(inOrder(result[i - 1], result[i]), `${JSON.stringify(result[i - 1])} is placed before ${JSON.stringify(result[i])}`);
  }
}

test('orderWithKey orders the five sample bookings', () => {
  assert.equal(orderWithKey(SAMPLE).map((b) => b.id).join(','), EXPECTED_IDS.join(','));
});

test('orderWithPasses orders the five sample bookings', () => {
  assert.equal(orderWithPasses(SAMPLE).map((b) => b.id).join(','), EXPECTED_IDS.join(','));
});

test('both functions return a new list and leave the input as it was', () => {
  const before = JSON.stringify(SAMPLE);
  orderWithKey(SAMPLE);
  orderWithPasses(SAMPLE);
  assert.equal(JSON.stringify(SAMPLE), before);
});

test('on 200 random lists, both functions give a correct order', () => {
  let seed = 11;
  const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
  const fares = [450, 900, 1250, 1400];
  for (let k = 0; k < 200; k++) {
    const n = Math.floor(random() * 31);
    const used = new Set();
    const bookings = [];
    while (bookings.length < n) {
      const id = 1 + Math.floor(random() * 999);
      if (used.has(id)) continue;
      used.add(id);
      bookings.push({ id, day: Math.floor(random() * 4), fare: fares[Math.floor(random() * 4)] });
    }
    check(orderWithKey(bookings), bookings);
    check(orderWithPasses(bookings), bookings);
  }
});

Interview questions

What do stable, in-place and adaptive mean for a sort?

A stable sort keeps items with equal keys in the order they had in the input, which is what makes sorting by several keys in several passes work. An in-place sort rearranges the items inside the storage they already occupy and keeps only a small amount of bookkeeping, such as quicksort’s ranges, plus a constant number of items outside the array. An adaptive sort runs faster when the input is already partly in order: insertion sort makes n − 1 comparisons on sorted input, and Python’s sort found and merged existing runs. The three properties are independent. Insertion sort has all three, selection sort is in place but neither stable nor adaptive, and array merge sort is stable but needs a buffer of n items.

Key takeaways

• Stable: equal keys keep their input order. In place: the items stay in their own storage, with little extra memory. Adaptive: less work on input that is already partly sorted.
• For a multi-key order, sort once by a key tuple, or run stable sorts from the least important key to the most important one.
• Stable by promise: Python’s sorts, JavaScript’s sort, Java’s List.sort, std::stable_sort and Go’s SortStableFunc and SliceStable. Not guaranteed: std::sort, slices.SortFunc, sort.Sort and sort.Slice.
• JavaScript sorts numbers as strings unless you pass a comparator such as (a, b) => a - b.
• Python’s sort is adaptive: 9,999 comparisons on 10,000 sorted items against 120,163 on shuffled ones.