Data Structures & Algorithms (DSA) Module 21 – Algorithms in practice

Why constant factors matter: caches and locality

How caches, cache lines and locality decide the speed of array scans, linked lists and tree searches, measured, and when a slower algorithm wins.

Advanced
25 minutes
Examples run with Python 3.14.8, Pyodide 314.0.7, Node.js 24.21.0 and quickjs 0.32.0
By MySmartCoPilot

What you will learn

Explain spatial and temporal locality
Measure the cost of pointer chasing against array scans
Decide when a theoretically slower algorithm wins in practice

Before you start

What you’ll learn · Before you start

What you will learn

Explain spatial and temporal locality
Measure the cost of pointer chasing against array scans
Decide when a theoretically slower algorithm wins in practice

Before you start

On this page

Big-O notation counts steps and treats every step as costing the same. On a real computer they do not: reading a number that sits in the processor’s nearest cache takes a nanosecond or two, while reading one from main memory can take a hundred nanoseconds or more. So two algorithms with the same Big-O can differ in speed by a factor of 10 or 100, only because of where their data lives and in what order they touch it. The hidden constant that Big-O drops is mostly memory. This lesson measures it: the memory staircase, row and column order, arrays against linked nodes, binary search against a tree and the branches of a loop, and then the small inputs where an O(n²) algorithm beats an O(n log n) one.

Memory is a staircase

Between the processor and main memory sit caches: small, fast memories that keep copies of recently used data. They come in levels. The first-level (L1) cache is tiny and answers within a few processor cycles; the second level (L2) is larger and slower; main memory (DRAM) holds everything and is slowest of all. When the processor reads an address, the nearest level that holds a copy answers.

Caches never fetch a single number. They copy memory in fixed-size blocks called cache lines, so reading one byte brings its neighbours along. Drepper’s survey of memory describes 64-byte lines as the norm; the Apple M5 Pro that recorded the outputs on this page uses 128-byte lines, and its operating system reports 128 KB of L1 data cache for each of its fastest cores and 16 MB of L2 cache shared by each group of six cores.

The program below measures the staircase. It builds an array whose slots hold the index of the next slot to visit, in one random cycle through every slot, and follows the chain: each read says where the next read is, so no read can start before the previous one has finished. The time per step is then close to the time of one read. Only the size of the array changes from row to row.

One read at a time, in arrays from 16 KiB to 256 MiB JavaScript · staircase.mjs

// The memory staircase: follow a chain of indexes through one random cycle that visits every slot of an array.
// Each read tells the program where the next read is, so the processor cannot start a read before the one before it
// has finished, and the time per step is close to the time one read from memory takes. Only the size of the array
// changes from row to row: the work per step is the same.

const inNode = typeof process !== 'undefined' && typeof process.cpuUsage === 'function';
// Node.js: the processor time of this program, which leaves out time spent waiting while other programs ran.
// Engines without Node.js have only the wall clock.
const now = inNode
  ? () => {
      const u = process.cpuUsage();
      return (u.user + u.system) / 1000;
    }
  : () => Date.now();

/** A random cycle through the slots 0 … n − 1 (Sattolo's shuffle), from a seeded generator: the same every run. */
function randomCycle(n, seed) {
  const next = new Int32Array(n);
  for (let i = 0; i < n; i++) next[i] = i;
  let s = seed >>> 0;
  for (let i = n - 1; i > 0; i--) {
    s = (Math.imul(s, 1664525) + 1013904223) >>> 0;
    const j = s % i; // 0 … i − 1, never i itself: that is what makes one cycle
    const t = next[i];
    next[i] = next[j];
    next[j] = t;
  }
  return next;
}

/** Follow the chain for `steps` steps from slot 0 and return where it ends. */
function chase(next, steps) {
  let p = 0;
  for (let k = 0; k < steps; k++) p = next[p];
  return p;
}

const KiB = 1024;
// Smaller sizes outside Node.js: the browser's interpreter is slower and has less memory.
const sizesKiB = inNode ? [16, 256, 4096, 32768, 262144] : [16, 256, 4096, 16384];
const steps = inNode ? 4_000_000 : 300_000;

console.log(`engine: ${inNode ? `Node.js ${process.versions.node}` : 'not Node.js'}`);
console.log('array size   ns per step');
for (const kib of sizesKiB) {
  const next = randomCycle((kib * KiB) / 4, 7 + kib); // 4-byte slots
  chase(next, Math.min(next.length, steps)); // warm up: load what fits into the caches
  let best = Infinity;
  for (let round = 0; round < 3; round++) {
    const t0 = now();
    const end = chase(next, steps);
    best = Math.min(best, now() - t0);
    if (end < 0 || end >= next.length) throw new Error('the chain left the array');
  }
  const size = kib >= KiB ? `${kib / KiB} MiB` : `${kib} KiB`;
  console.log(`${size.padStart(10)}   ${((best * 1e6) / steps).toFixed(1).padStart(11)}`);
}

Output

engine: Node.js 24.21.0
array size   ns per step
    16 KiB           2.3
   256 KiB           8.0
     4 MiB          46.9
    32 MiB         125.2
   256 MiB         142.1

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node staircase.mjs

Version note

The Run button runs this file in QuickJS, a JavaScript interpreter compiled to WebAssembly, so it prints not Node.js as the engine and stops at 16 MiB. An interpreter spends tens of nanoseconds on every step whatever the array size, so its staircase starts higher and its steps look smaller than in Node.js.

The instruction never changes, yet a step costs about 2 ns while the array fits in the L1 cache and about 140 ns once it is many times larger than every cache: roughly 60 times as long. The recorded run timed the program with its own processor time, because other programs were running on the computer and sharing its caches, so read the shape rather than the exact steps: every computer has such a staircase, with stairs at its own cache sizes.

The recording computer's memory levels and the measured time per read

Text description of the diagram

The diagram is a column of four boxes joined by arrows from top to bottom. A read goes down the column until a level holds the data.

The processor.
The L1 data cache, 128 KB for each of the fastest cores. A chain of reads through a 16 KiB array, which fits in it, took 2.3 ns per read.
The L2 cache, 16 MB shared by each group of six cores, reached when the L1 cache misses. Arrays of 256 KiB and 4 MiB fit in it and took 8.0 ns and 46.9 ns per read.
Main memory, 48 GB, reached when the L2 cache misses too. Arrays of 32 MiB and 256 MiB fit only here and took 125.2 ns and 142.1 ns per read.

Spatial and temporal locality

Caches pay off because programs rarely touch memory at random. Two habits, called locality, make the copies useful:

Spatial locality: using data close to data you just used. Reading the next element of an array uses the rest of a cache line that is already loaded.
Temporal locality: using the same data again soon, while its line is still in the cache, such as the variables of a loop or the top of a search tree that every search passes through.

A grid makes spatial locality visible. Stored row after row in one block, a grid of 8-byte numbers has 16 neighbours of a row in every 128-byte line. Adding it up row by row uses all 16 numbers of each line it loads; adding it column by column uses one number from a line, then jumps a whole row ahead.

The same sum, row by row and column by column JavaScript · grid.mjs

// Sum the same grid of numbers twice: row by row, and column by column. The grid is stored row after row in one
// Float64Array (8 bytes a number), so going along a row reads neighbouring bytes, while going down a column jumps a
// whole row ahead at every step. Both orders add the same numbers the same number of times.

const inNode = typeof process !== 'undefined' && typeof process.cpuUsage === 'function';
// Node.js: the processor time of this program (it leaves out time spent waiting while other programs ran).
const now = inNode
  ? () => {
      const u = process.cpuUsage();
      return (u.user + u.system) / 1000;
    }
  : () => Date.now();

function byRows(grid, n) {
  let total = 0;
  for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) total += grid[r * n + c];
  return total;
}

function byColumns(grid, n) {
  let total = 0;
  for (let c = 0; c < n; c++) for (let r = 0; r < n; r++) total += grid[r * n + c];
  return total;
}

/** The fastest of `rounds` runs of f, in milliseconds, and what f returned. */
function fastest(f, rounds) {
  let best = Infinity;
  let result;
  for (let i = 0; i < rounds; i++) {
    const t0 = now();
    result = f();
    best = Math.min(best, now() - t0);
  }
  return { ms: best, result };
}

console.log(`engine: ${inNode ? `Node.js ${process.versions.node}` : 'not Node.js'}`);
let agree = true;
for (const n of inNode ? [512, 4096] : [256, 1024]) {
  const grid = new Float64Array(n * n);
  for (let i = 0; i < grid.length; i++) grid[i] = i % 10;
  byRows(grid, n); // warm up
  byColumns(grid, n);
  const rows = fastest(() => byRows(grid, n), 5);
  const cols = fastest(() => byColumns(grid, n), 5);
  if (rows.result !== cols.result) agree = false;
  const mib = (n * n * 8) / 1048576;
  const size = mib >= 1 ? `${mib} MiB` : `${mib * 1024} KiB`;
  console.log(`${n} x ${n} grid (${size}): rows ${rows.ms.toFixed(1)} ms, columns ${cols.ms.toFixed(1)} ms, ${(cols.ms / rows.ms).toFixed(1)} times as long`);
}
console.log(`both orders gave the same sums: ${agree}`);

Output

engine: Node.js 24.21.0
512 x 512 grid (2 MiB): rows 0.2 ms, columns 0.6 ms, 2.7 times as long
4096 x 4096 grid (128 MiB): rows 14.3 ms, columns 106.4 ms, 7.4 times as long
both orders gave the same sums: true

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node grid.mjs

Both orders add the same numbers, the same number of times, in O(n²) for an n × n grid. In the 2 MiB grid, one column pass touches 512 lines, 64 KiB, which the L1 cache can keep, and column order still took about 3 times as long: even when every line is cached, jumping 4 KB at every step costs the processor more than reading neighbours. In the 128 MiB grid, one column pass touches 4,096 different lines, 512 KiB, four times what the L1 cache holds, so the line a read needs has almost always been pushed out of it since the previous column, and the gap grew to about 7 times. The fix is to follow the layout: let the inner loop walk along a row, or, when an algorithm needs columns, transpose the data first so that it reads them in order.

Pointer chasing: arrays against linked nodes

An array keeps its items in one block, so a scan reads memory in order, and processors detect that pattern and prefetch the next lines before they are asked for. A linked list keeps each item in a separate node that holds a reference to the next one, so reading item i + 1 means first loading node i to learn where it is. This is pointer chasing, and whether it is fast depends on where the nodes happen to be:

An array, and linked nodes in creation order and in shuffled order JavaScript · nodes.mjs

// The same numbers summed three ways: from an array, by following linked nodes that were created in list order, and
// by following linked nodes that are linked in a shuffled order. All three are O(n) and add the same numbers.

const inNode = typeof process !== 'undefined' && typeof process.cpuUsage === 'function';
// Node.js: the processor time of this program (it leaves out time spent waiting while other programs ran).
const now = inNode
  ? () => {
      const u = process.cpuUsage();
      return (u.user + u.system) / 1000;
    }
  : () => Date.now();

const n = inNode ? 1 << 20 : 1 << 17;

/** A seeded shuffle of 0 … n − 1 (Fisher-Yates): the same order every run. */
function shuffledOrder(count, seed) {
  const order = Array.from({ length: count }, (_, i) => i);
  let s = seed >>> 0;
  for (let i = count - 1; i > 0; i--) {
    s = (Math.imul(s, 1664525) + 1013904223) >>> 0;
    const j = s % (i + 1);
    [order[i], order[j]] = [order[j], order[i]];
  }
  return order;
}

const values = Array.from({ length: n }, (_, i) => i % 1000);

// Nodes created one after another and linked in the same order: neighbours in the list were created together.
const inOrder = values.map((value) => ({ value, next: null }));
for (let i = 0; i + 1 < n; i++) inOrder[i].next = inOrder[i + 1];

// The same kind of nodes, linked in a shuffled order: the next node was created at some random other moment.
const order = shuffledOrder(n, 11);
const scattered = values.map(() => ({ value: 0, next: null }));
for (let k = 0; k < n; k++) scattered[order[k]].value = values[k];
for (let k = 0; k + 1 < n; k++) scattered[order[k]].next = scattered[order[k + 1]];

const sumArray = () => {
  let total = 0;
  for (let i = 0; i < values.length; i++) total += values[i];
  return total;
};
const sumList = (head) => {
  let total = 0;
  for (let node = head; node !== null; node = node.next) total += node.value;
  return total;
};

const ways = [
  ['array, by index', sumArray],
  ['nodes linked in creation order', () => sumList(inOrder[0])],
  ['nodes linked in shuffled order', () => sumList(scattered[order[0]])],
];
console.log(`engine: ${inNode ? `Node.js ${process.versions.node}` : 'not Node.js'}`);
const withCommas = (x) => String(x).replace(/\B(?=(\d{3})+(?!\d))/g, ',');
console.log(`${withCommas(n)} numbers, nanoseconds per number:`);
const totals = new Set();
for (const [name, f] of ways) {
  f(); // warm up
  let best = Infinity;
  for (let round = 0; round < 5; round++) {
    const t0 = now();
    totals.add(f());
    best = Math.min(best, now() - t0);
  }
  console.log(`  ${name.padEnd(31)} ${((best * 1e6) / n).toFixed(1).padStart(6)}`);
}
console.log(`all three totals agree: ${totals.size === 1}`);

Output

engine: Node.js 24.21.0
1,048,576 numbers, nanoseconds per number:
  array, by index                    0.8
  nodes linked in creation order     1.7
  nodes linked in shuffled order   135.0
all three totals agree: true

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node nodes.mjs

All three loops are O(n) and add the same million numbers. The nodes created one after another evidently sit next to each other in memory, since following them cost only about twice the array: nearly a scan. Linked in a shuffled order, the same kind of nodes cost over 100 times the array per number: every step lands somewhere unpredictable, the prefetcher cannot guess it, and the next step waits for main memory. Lists in long-running programs drift towards the shuffled case, because nodes inserted at different times are allocated at different places.

Python adds a twist: a list is not a block of numbers. CPython’s documentation describes a list as a contiguous array of references to objects, and every integer above 256 is a separate object (CPython keeps ready-made objects only for −5 to 256). So even sum() over a list follows a pointer for every item:

sum() over the same integers, before and after a shuffle Python · shuffled_sum.py

# sum() over the same million integers twice: in the order they were created, and after shuffling the list.
# The values, the count and the algorithm are the same; only the order of the references in the list changes.
import random
import time


def fastest(f, rounds=5):
    """The fastest of several runs of f, in seconds of processor time (other programs' time is left out)."""
    best = float("inf")
    for _ in range(rounds):
        start = time.process_time()
        f()
        best = min(best, time.process_time() - start)
    return best


n = 1_000_000
in_order = list(range(10**6, 10**6 + n))  # numbers above 256: each one a separate object, created in this order
shuffled = in_order[:]
random.Random(42).shuffle(shuffled)

a = fastest(lambda: sum(in_order))
b = fastest(lambda: sum(shuffled))
print(f"{n:,} integers, nanoseconds per integer:")
print(f"  sum() in creation order  {a * 1e9 / n:5.1f}")
print(f"  sum() after a shuffle    {b * 1e9 / n:5.1f}")
print(f"same total: {sum(in_order) == sum(shuffled)}")

Output

1,000,000 integers, nanoseconds per integer:
  sum() in creation order    3.8
  sum() after a shuffle     21.9
same total: True

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 shuffled_sum.py

The integer objects were created in order, so in the original list neighbouring references point to neighbouring objects. Shuffling the list moves only the references; the objects stay where they are, so sum() now visits them in a random order, and the same one-line program took nearly 6 times as long. When a Python program crunches millions of numbers, a structure that stores the numbers themselves, such as array.array from the arrays lesson, avoids both the references and the scattered objects.

Same comparisons, different layout

Binary search over a sorted array and a search down a balanced binary search tree can make exactly the same comparisons: the tree below is built so that each node holds the middle key of its part of the array, the key binary search would look at. Both searches are O(log n) and stop at the same moment. The layouts differ: the array holds 4-byte keys side by side, and the tree holds a separate object for every key with two references in it.

Binary search in a sorted array against a balanced tree JavaScript · lookups.mjs

// Look keys up in the same sorted keys two ways: binary search in a sorted array, and a search down a perfectly
// balanced binary search tree built from that array. Both compare the key with the same middle elements in the same
// order and stop at the same moment, so they do the same work in O(log n) steps; only the memory layout differs.

const inNode = typeof process !== 'undefined' && typeof process.cpuUsage === 'function';
// Node.js: the processor time of this program (it leaves out time spent waiting while other programs ran).
const now = inNode
  ? () => {
      const u = process.cpuUsage();
      return (u.user + u.system) / 1000;
    }
  : () => Date.now();

function binarySearch(keys, x) {
  let lo = 0;
  let hi = keys.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    const k = keys[mid];
    if (k === x) return true;
    if (k < x) lo = mid + 1;
    else hi = mid - 1;
  }
  return false;
}

/** The balanced tree whose root is the middle of keys[lo … hi], as binary search sees it. */
function buildTree(keys, lo, hi) {
  if (lo > hi) return null;
  const mid = (lo + hi) >> 1;
  return { key: keys[mid], left: buildTree(keys, lo, mid - 1), right: buildTree(keys, mid + 1, hi) };
}

function treeSearch(root, x) {
  let node = root;
  while (node !== null) {
    if (x === node.key) return true;
    node = x < node.key ? node.left : node.right;
  }
  return false;
}

function timeLookups(search, queries) {
  let found = 0;
  for (let q = 0; q < queries.length; q++) if (search(queries[q])) found++;
  return found;
}

const sizes = inNode ? [1 << 10, 1 << 16, 1 << 20] : [1 << 10, 1 << 14];
const queryCount = inNode ? 600_000 : 30_000;
const withCommas = (x) => String(x).replace(/\B(?=(\d{3})+(?!\d))/g, ',');

console.log(`engine: ${inNode ? `Node.js ${process.versions.node}` : 'not Node.js'}`);
console.log('      keys   sorted array   balanced tree   tree / array');
for (const n of sizes) {
  const keys = new Int32Array(n);
  for (let i = 0; i < n; i++) keys[i] = 2 * i; // even numbers: half the queries below are present
  const root = buildTree(keys, 0, n - 1);
  const queries = new Int32Array(queryCount);
  let s = 3;
  for (let i = 0; i < queryCount; i++) {
    s = (Math.imul(s, 1664525) + 1013904223) >>> 0;
    queries[i] = s % (2 * n);
  }
  const ways = [(x) => binarySearch(keys, x), (x) => treeSearch(root, x)];
  const ns = [];
  const found = [];
  for (const search of ways) {
    timeLookups(search, queries); // warm up
    let best = Infinity;
    for (let round = 0; round < 3; round++) {
      const t0 = now();
      found.push(timeLookups(search, queries));
      best = Math.min(best, now() - t0);
    }
    ns.push((best * 1e6) / queryCount);
  }
  if (new Set(found).size !== 1) throw new Error('the two searches disagree');
  console.log(`${withCommas(n).padStart(10)}   ${ns[0].toFixed(1).padStart(9)} ns   ${ns[1].toFixed(1).padStart(10)} ns   ${(ns[1] / ns[0]).toFixed(1).padStart(12)}`);
}

Output

engine: Node.js 24.21.0
      keys   sorted array   balanced tree   tree / array
     1,024        20.6 ns         32.6 ns            1.6
    65,536       135.7 ns        262.2 ns            1.9
 1,048,576       289.2 ns        833.3 ns            2.9

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node lookups.mjs

With 1,024 keys everything fits in the L1 cache in both layouts, and the tree still took about one and a half times as long, because reaching a key through an object costs more than reading it from an array. With a million keys the tree took almost 3 times as long: the first few comparisons of every search hit the same middle keys, which stay cached (temporal locality), but the deeper levels are different for every key, and a compact array keeps far more of them in the caches than a set of objects does. This is the reason databases store their indexes as B-trees, whose nodes pack hundreds of keys into one block (the red-black and B-trees lesson): fewer, fuller nodes mean fewer slow reads per search.

Branches are constant factors too

Memory is not the only cost that Big-O hides. A processor works through instructions far ahead of the one it is finishing, so at an if it guesses which way the test will go and carries on. A right guess costs nearly nothing; a wrong one throws away the work done on the wrong path. Drepper’s survey notes how much processors invest in this branch prediction. Data decides how well it works:

One loop with an if, on random and on sorted bytes JavaScript · branches.mjs

// Add up the bytes of at least 128 in an array of random bytes, then in the same bytes sorted. The work is the same:
// the same reads in the same order and the same additions. Only the pattern of the "if" changes: in sorted data it
// is false for the whole first half and true for the whole second half; in random data it is a coin toss.

const inNode = typeof process !== 'undefined' && typeof process.cpuUsage === 'function';
// Node.js: the processor time of this program (it leaves out time spent waiting while other programs ran).
const now = inNode
  ? () => {
      const u = process.cpuUsage();
      return (u.user + u.system) / 1000;
    }
  : () => Date.now();

function sumLarge(bytes) {
  let total = 0;
  for (let i = 0; i < bytes.length; i++) {
    if (bytes[i] >= 128) total += bytes[i];
  }
  return total;
}

const n = inNode ? 1 << 24 : 1 << 19;
const random = new Uint8Array(n);
let s = 99;
for (let i = 0; i < n; i++) {
  s = (Math.imul(s, 1664525) + 1013904223) >>> 0;
  random[i] = s >>> 24;
}
const sorted = Uint8Array.from(random).sort();

console.log(`engine: ${inNode ? `Node.js ${process.versions.node}` : 'not Node.js'}`);
const totals = [];
for (const [name, bytes] of [['random order', random], ['sorted', sorted]]) {
  sumLarge(bytes); // warm up
  let best = Infinity;
  for (let round = 0; round < 5; round++) {
    const t0 = now();
    totals.push(sumLarge(bytes));
    best = Math.min(best, now() - t0);
  }
  console.log(`${name.padEnd(12)} ${((best * 1e6) / n).toFixed(2)} ns per byte`);
}
console.log(`same total both times: ${new Set(totals).size === 1}`);

Output

engine: Node.js 24.21.0
random order 5.05 ns per byte
sorted       1.14 ns per byte
same total both times: true

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node branches.mjs

Version note

The Run button runs this file in QuickJS, which interprets every instruction instead of compiling the loop, so the interpreter’s own work dwarfs a wrong guess and the two times come out close, in either order.

Sorted, the test bytes[i] >= 128 is false for the whole first half and true for the whole second half, so the guesses are right; on random bytes it is a coin toss, and the same loop over the same bytes took about 4 times as long. Do not turn this into a rule to sort data first: sorting costs far more than it saves here, and a compiler may replace such an if with an instruction that needs no guess, which removes the difference. Measure before believing it either way.

Small inputs: when the slower algorithm wins

Big-O describes growth, and growth needs large n. For small n the constant factors decide, and they favour simple loops. Insertion sort is O(n²) and merge sort O(n log n), but insertion sort makes no copies and no calls, while merge sort splits, recurses and merges. This program finds where the order changes, then uses the answer:

Insertion sort against merge sort, and a hybrid Python · crossover.py

# Insertion sort is O(n^2) and merge sort O(n log n), so merge sort must win for large n. This finds where it starts
# winning, by timing both on the same random lists, then uses the answer: merge sort that hands short pieces to
# insertion sort.
import random
import time


def insertion_sort(a):
    for i in range(1, len(a)):
        x = a[i]
        j = i - 1
        while j >= 0 and a[j] > x:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a


def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


def merge_sort(a, cutoff=1):
    """Merge sort; pieces of at most `cutoff` items go to insertion sort (cutoff 1: plain merge sort)."""
    if len(a) <= cutoff:
        return insertion_sort(a)
    mid = len(a) // 2
    return merge(merge_sort(a[:mid], cutoff), merge_sort(a[mid:], cutoff))


def fastest(f, rounds=3):
    """The fastest of several runs of f, in seconds of processor time (other programs' time is left out)."""
    best = float("inf")
    for _ in range(rounds):
        start = time.process_time()
        f()
        best = min(best, time.process_time() - start)
    return best


rng = random.Random(7)
print("    n   insertion   merge (microseconds per list)")
last_insertion_win = None
for n in (8, 16, 32, 48, 64, 96, 128, 256):
    lists = [[rng.random() for _ in range(n)] for _ in range(max(20, 12_000 // n))]
    ins = fastest(lambda: [insertion_sort(x[:]) for x in lists]) / len(lists)
    mrg = fastest(lambda: [merge_sort(x[:]) for x in lists]) / len(lists)
    if ins < mrg:
        last_insertion_win = n
    print(f"{n:5}   {ins * 1e6:9.1f}   {mrg * 1e6:5.1f}   {'insertion' if ins < mrg else 'merge'} sort was faster")
print(f"insertion sort was faster up to n = {last_insertion_win} in this run")

data = [rng.random() for _ in range(10_000)]
print("merge sort of 10,000 numbers, short pieces to insertion sort:")
for cutoff in (1, 8, 16, 32, 64, 128):
    t = fastest(lambda: merge_sort(data[:], cutoff))
    assert merge_sort(data[:], cutoff) == sorted(data)
    print(f"  pieces up to {cutoff:3}: {t * 1e3:5.1f} ms")

Output

    n   insertion   merge (microseconds per list)
    8         1.2     5.3   insertion sort was faster
   16         3.5    12.9   insertion sort was faster
   32        11.6    26.1   insertion sort was faster
   48        24.6    46.9   insertion sort was faster
   64        43.1    62.1   insertion sort was faster
   96        90.8    89.6   merge sort was faster
  128       164.0   134.2   merge sort was faster
  256       615.2   273.0   merge sort was faster
insertion sort was faster up to n = 64 in this run
merge sort of 10,000 numbers, short pieces to insertion sort:
  pieces up to   1:  15.8 ms
  pieces up to   8:  11.2 ms
  pieces up to  16:  11.3 ms
  pieces up to  32:  10.7 ms
  pieces up to  64:  12.6 ms
  pieces up to 128:  15.0 ms

This output changes from run to run: the times depend on the computer, the runtime and what else the computer is doing

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 crossover.py

In the recorded run insertion sort was faster up to 64 items, the two were within about 1 % at 96, and from 128 on merge sort pulled away. Handing pieces of 8 to 32 items to insertion sort made merge sort of 10,000 numbers about a third faster than plain merge sort; pieces of 128 items gained almost nothing, because insertion sort’s n² takes over.

Standard libraries are built the same way. CPython’s list.sort() sorts a whole list of fewer than 64 items with binary insertion sort and extends short runs to a minimum length between 32 and 64 with it, according to the notes and the source of its implementation. Java documents Arrays.sort(int[]) as a dual-pivot quicksort, and the OpenJDK source behind it switches to insertion sort for parts of fewer than 44 elements. The crossover depends on the language and the computer, which is why library authors measure it rather than derive it.

Big-O chooses the family, measurement chooses the winner

Choose the growth rate first. No layout trick rescues an O(n²) algorithm at a million items; constant factors decide between algorithms of the same growth, and below the crossover.
Prefer contiguous data for anything you scan. Arrays, array-backed lists and heaps, and typed arrays read memory in order; linked nodes pay a pointer chase per item.
Keep the data you reuse small. Compact types (an array.array instead of a list of objects, a 4-byte key instead of an object) let more of it stay in the caches.
Measure with realistic sizes and data. The staircase moves with the cache sizes, and sorted, random and real data behave differently.
Write down what you measured on: the processor, the runtime and its version, as every output on this page does.

Algorithms that are efficient for every cache size without being tuned to any, called cache-oblivious algorithms (Frigo, Leiserson, Prokop and Ramachandran), are the next step for readers who want the theory behind these rules.

JavaScript & TypeScript Online Compiler Run the staircase with your own array sizes and see where your computer's stairs are.

Exercise: count the cache misses

Exercise · Medium · Python, JavaScript

Count the cache misses of row and column order

Timings change from run to run, so this exercise counts cache misses with a small model of a cache instead: the same count on every computer. Write two functions (in JavaScript, gridAddresses and countMisses):

- grid_addresses(rows, cols, item_size, order) returns the byte address of every item of a grid stored row after row from address 0, in the order a loop visits them: order is "rows" (row by row) or "columns" (column by column). The item in row r and column c is at (r * cols + c) * item_size. - count_misses(addresses, line_size, capacity) replays the addresses through a cache that holds capacity lines of line_size bytes. An address falls in line address // line_size. A read whose line is in the cache is a hit; otherwise it is a miss, and the line is loaded. When the cache is full, loading a line first evicts the line that was used least recently. Return the number of misses.

For example, a 2 × 3 grid of 8-byte items has the addresses 0, 8, 16, 24, 32, 40 row by row, and 0, 24, 8, 32, 16, 40 column by column. With 16-byte lines and room for 1 line, row order misses 3 times and column order 6 times.

Python · Starter code · misses.py

def grid_addresses(rows, cols, item_size, order):
    """Byte addresses of a row-major grid, visited row by row (order="rows") or column by column (order="columns")."""
    return []


def count_misses(addresses, line_size, capacity):
    """Misses of a cache of `capacity` lines of `line_size` bytes that evicts the least recently used line."""
    return 0

The sample tests · test_misses.py

from misses import count_misses, grid_addresses


def test_grid_addresses():
    """visits a 2 x 3 grid of 8-byte items row by row and column by column"""
    assert grid_addresses(2, 3, 8, "rows") == [0, 8, 16, 24, 32, 40]
    assert grid_addresses(2, 3, 8, "columns") == [0, 24, 8, 32, 16, 40]


def test_hits_inside_a_line():
    """reads inside a line that is already cached are hits"""
    assert count_misses([0, 8, 16, 64, 0], 64, 2) == 2
    assert count_misses([0, 64, 0, 64], 64, 1) == 4


def test_least_recently_used():
    """evicts the line used least recently, not the one loaded first"""
    assert count_misses([0, 64, 0, 128, 64], 64, 2) == 4
    assert count_misses([0, 64, 0, 128, 0], 64, 2) == 3


def test_example_from_the_prompt():
    """a 2 x 3 grid with 16-byte lines and room for 1 line"""
    assert count_misses(grid_addresses(2, 3, 8, "rows"), 16, 1) == 3
    assert count_misses(grid_addresses(2, 3, 8, "columns"), 16, 1) == 6


def test_row_order_uses_every_line_once():
    """an 8 x 8 grid of 8-byte items with 64-byte lines: one line per row"""
    assert count_misses(grid_addresses(8, 8, 8, "rows"), 64, 4) == 8


def test_column_order_misses_when_the_rows_do_not_fit():
    """column order misses on every read when the cache holds fewer lines than the grid has rows"""
    assert count_misses(grid_addresses(8, 8, 8, "columns"), 64, 4) == 64
    assert count_misses(grid_addresses(8, 8, 8, "columns"), 64, 8) == 8
    assert count_misses(grid_addresses(64, 64, 8, "columns"), 64, 32) == 4096
    assert count_misses(grid_addresses(64, 64, 8, "rows"), 64, 32) == 512

JavaScript · Starter code · misses.mjs

/** Byte addresses of a row-major grid, visited row by row (order "rows") or column by column (order "columns"). */
export function gridAddresses(rows, cols, itemSize, order) {
  return [];
}

/** Misses of a cache of `capacity` lines of `lineSize` bytes that evicts the least recently used line. */
export function countMisses(addresses, lineSize, capacity) {
  return 0;
}

The sample tests · misses.test.mjs

import { test, assert } from 'mysmartcopilot:test';
import { countMisses, gridAddresses } from './misses.mjs';

test('visits a 2 x 3 grid of 8-byte items row by row and column by column', () => {
  assert.deepEqual(gridAddresses(2, 3, 8, 'rows'), [0, 8, 16, 24, 32, 40]);
  assert.deepEqual(gridAddresses(2, 3, 8, 'columns'), [0, 24, 8, 32, 16, 40]);
});
test('reads inside a line that is already cached are hits', () => {
  assert.equal(countMisses([0, 8, 16, 64, 0], 64, 2), 2);
  assert.equal(countMisses([0, 64, 0, 64], 64, 1), 4);
});
test('evicts the line used least recently, not the one loaded first', () => {
  assert.equal(countMisses([0, 64, 0, 128, 64], 64, 2), 4);
  assert.equal(countMisses([0, 64, 0, 128, 0], 64, 2), 3);
});
test('a 2 x 3 grid with 16-byte lines and room for 1 line', () => {
  assert.equal(countMisses(gridAddresses(2, 3, 8, 'rows'), 16, 1), 3);
  assert.equal(countMisses(gridAddresses(2, 3, 8, 'columns'), 16, 1), 6);
});
test('an 8 x 8 grid of 8-byte items with 64-byte lines: one line per row', () => {
  assert.equal(countMisses(gridAddresses(8, 8, 8, 'rows'), 64, 4), 8);
});
test('column order misses on every read when the cache holds fewer lines than the grid has rows', () => {
  assert.equal(countMisses(gridAddresses(8, 8, 8, 'columns'), 64, 4), 64);
  assert.equal(countMisses(gridAddresses(8, 8, 8, 'columns'), 64, 8), 8);
  assert.equal(countMisses(gridAddresses(64, 64, 8, 'columns'), 64, 32), 4096);
  assert.equal(countMisses(gridAddresses(64, 64, 8, 'rows'), 64, 32), 512);
});

A hint

Keep the cached line numbers in order of last use: Python's collections.OrderedDict (move_to_end, and popitem(last=False) to evict the oldest) or a JavaScript Map, whose keys stay in insertion order (delete a key and set it again to make it the newest). A hit moves its line to the newest end; a miss adds it there, after evicting the oldest line if the cache already holds capacity lines.

The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Check yourself

GATE CS

The GATE 2027 syllabus for Computer Science and Information Technology lists “Memory interfacing and hierarchy: performance, cache memory mapping” under Computer Organization and Architecture. Those questions are about the hardware side of this lesson (how addresses map to cache lines and how hit ratios set the average access time), and GATE asks them as multiple-choice and numerical questions with no program to run.

Interview questions

What are spatial and temporal locality, and why do caches depend on them? Spatial locality means a program uses data close to data it has just used, as a loop over an array does; temporal locality means it uses the same data again soon, as the variables of a loop are. Caches copy memory in whole lines, 64 or 128 bytes at a time, and keep recently used lines, so spatial locality makes the rest of each line useful and temporal locality makes the kept lines useful. A program with neither, such as one that follows pointers to scattered objects, misses the cache on most reads and waits for main memory, which in this lesson’s measurement took about 60 times as long per read as the L1 cache.

Why can an algorithm with a worse Big-O run faster in practice? Big-O keeps only the growth rate and drops constant factors, and on small inputs the constant factors decide. Insertion sort does a few simple operations per step, with no copies and no calls, while merge sort splits, recurses and allocates, so in this lesson’s run insertion sort was faster up to 64 items. Memory adds another constant factor: an O(n) scan of an array can beat an O(n) walk of linked nodes by a factor of 100. This is why libraries combine algorithms, such as merge sort that hands short pieces to insertion sort. Big-O still decides for large n.

Key takeaways

Where the data sits decides what a read costs: about 2 ns in the L1 cache and about 140 ns in main memory in this lesson’s run, so the access pattern can change the speed of one algorithm by a factor of 10 to 100.
Caches load whole lines and keep recent ones: spatial locality uses the rest of each line, temporal locality reuses lines before they are evicted.
Scanning an array is fast; chasing pointers through scattered nodes or objects is slow, even in Python, where a list holds references.
Same comparisons in a more compact layout are faster: a balanced tree took almost 3 times as long as a sorted array at a million keys.
Unpredictable branches cost too, but measure before reorganising code around them.
For small n the simpler, theoretically slower algorithm often wins, which is why library sorts are hybrids.

References

What Every Programmer Should Know About Memory (U. Drepper, Red Hat) (Ulrich Drepper)
Design and History FAQ: how are lists implemented in CPython? (Python Software Foundation)
Integer objects: PyLong_FromLong and the small-integer cache (Python Software Foundation)
listsort.txt: the design of list.sort (CPython 3.14 source) (Python Software Foundation)
listobject.c: MAX_MINRUN (CPython 3.14 source) (Python Software Foundation)
Arrays.sort(int[]): implementation note (Java SE 25) (Oracle)
DualPivotQuicksort.java (OpenJDK 25 updates source) (OpenJDK)
Cache-oblivious algorithms (M. Frigo, C. E. Leiserson, H. Prokop and S. Ramachandran, FOCS 1999) (IEEE)
GATE 2027 syllabus for Computer Science and Information Technology (CS) (IIT Madras (GATE 2027 organising institute))

Report a problem with this lesson

Your country

Why constant factors matter: caches and locality

What you will learn

Before you start

What you will learn

Before you start

Memory is a staircase

Spatial and temporal locality

Pointer chasing: arrays against linked nodes

Same comparisons, different layout

Branches are constant factors too

Small inputs: when the slower algorithm wins

Big-O chooses the family, measurement chooses the winner

Exercise: count the cache misses

Count the cache misses of row and column order

Results of the sample tests

Check yourself

Check yourself

Interview questions

Key takeaways

References

Related tools