Sorting Networks

in progressThis lesson is still being built - content, demos, and checkpoints may change before release.

Sorting network

Loading interactive demo…

A sorting network is a fixed sequence of compare-exchange gates between positions: each gate compares two wires and swaps them if the lower one holds the bigger value. The sequence never depends on the data. This is Batcher's odd-even merge network, the construction GPUs still use. Take the tour, or press and explore. Legend:

The panel beside the stage is the real SortingNetwork class from the published library executing in your browser, with the current line highlighted.

The lower-index wire of the active gate (on a layer step, of every gate in that layer).
The other wire of the gate. The bracket points at the pair.
One of the two bands: the blocks being merged in the current phase alternate between this tint and the next.
The other band. Gates never cross from one block into its neighbour.
Every bar, once the whole array is sorted.

Because no two gates in a layer share a wire, a whole layer can fire at once: the network sorts in O(log² n) parallel steps. Shuffle and replay and the comparator count never moves, only the swaps do.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

A network built for $n = 2^m$ wires runs the same gates whatever the input, so best, average and worst case are one number. Batcher's odd-even merge of two sorted runs of length $p$ costs $M(2p) = 2M(p) + p - 1$ gates, and the whole sort is $S(n) = 2S(n/2) + M(n)$ , which closes to

S(n) = \frac{n}{4}\left(\log_2^2 n - \log_2 n + 4\right) - 1

gates: 5, 19, 63 and 191 for 4, 8, 16 and 32 wires, the fixed totals the comparators readout reaches every time. That is $O(n \log^2 n)$ work, more than merge sort's $O(n \log n)$ , but the gates of one layer touch disjoint wires, so with enough comparators the depth is only $\tfrac{1}{2}\log_2 n\,(\log_2 n + 1) = O(\log^2 n)$ parallel steps: ten layers for 16 wires. The sort is in place with $O(1)$ extra memory and not stable: a gate that reaches across several wires can carry a value past an equal one. Its access pattern is data-oblivious, which is exactly why hardware and secure computation like it.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

The nested loops are the network: p is the size of the sorted runs being merged (doubling), k the gate stride (halving from p to 1), and j and i walk the gates of one layer. The only line that reads the data is the final a[lo] > a[hi].
j starts at k % p: the first layer of a merge (k = p) pairs the two runs wire for wire, and every later layer starts k wires in, which is what makes it the odd-even merge.
The block test on Math.floor(lo / (2 * p)) keeps a gate inside one merge block of 2p wires; wires in different blocks belong to a later phase.
layer is emitted before its gates, so a layer step shows every gate about to fire at once; compare and swap snapshot the array before the exchange.
supports(n) uses the classic power-of-two test (n & (n - 1)) === 0 and refuses anything outside minSize to maxSize: a network exists only for the n it was built for, so the stage's slider moves over exponents rather than counts.
The swap emit sits inside the if, making the swap count the one readout that depends on the input.

A sorting network is a sort with no branches: a fixed list of compare-exchange gates, the same for every input, so it can be built from wires and comparators instead of written as a program. The idea was studied around 1954 by Armstrong, Nelson and O'Connor, who went on to patent a hardware sorting switch. The field took shape with Ken Batcher's 1968 paper, whose odd-even merge and bitonic constructions still run on GPUs today, and in 1983 Ajtai, Komlós and Szemerédi proved that networks of optimal depth exist at all.

c. 1954Armstrong, Nelson and O'Connor - Study the first sorting networks. O'Connor and Nelson's 'Sorting system with n-line sorting switch', filed in 1957, is granted as US patent 3,029,413 in 1962.source
1962R. C. Bose and R. J. Nelson - 'A Sorting Problem' in the Journal of the ACM: a recursive construction of comparator networks and the question of how few comparators can sort n inputs.source
1968Ken Batcher - 'Sorting Networks and Their Applications' at the AFIPS Spring Joint Computer Conference presents the odd-even merge and bitonic networks: O(n log² n) comparators in O(log² n) parallel depth.source
1973Donald Knuth - The Art of Computer Programming Vol. 3 devotes a section to networks for sorting, with the zero-one principle and tables of the best known networks.source
1983Ajtai, Komlós and Szemerédi - 'An O(n log n) sorting network' at STOC proves that networks of O(log n) depth exist, settling the asymptotic question.source

Used today

GPU and SIMD sorting - Bitonic and odd-even merge networks fire every gate of a layer in lockstep, exactly what thousands of GPU threads want.
Hardware sorters and switch fabrics - A network is a circuit: comparators wired once sort or route in fixed time, from Batcher's switching networks to median filters.
Data-oblivious computation - The access pattern never depends on the data, so networks sort inside secure multiparty computation and encrypted databases without leaking order.

Did you know

Ken Batcher spent 28 years as a computer architect at Goodyear Aerospace, designing the STARAN associative processor and the Massively Parallel Processor, 16,384 bit-serial processors now kept by the Smithsonian. The ACM/IEEE Eckert-Mauchly Award followed in 1990.source
The AKS network of 1983 has the best possible depth, but the constant hidden in its O(log n) is so large that it has never been used in practice: optimal in theory, useless on any real machine.source
Knuth's verdict on AKS versus Batcher: 'Batcher's method is much better, unless n exceeds the total memory capacity of all computers on earth!'source
M. W. Green's 16-input network from 1969 uses 60 comparators. More than half a century later nobody has beaten it, and nobody has proven it optimal: the best lower bound still sits a few comparators short.source

n16 = 2^4

comparators: 0
swaps: 0
layer: 0/10

sorting-network.ts

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Batcher's odd-even merge sort as a sorting network: a fixed schedule * of compare-exchange gates between wire positions. Runs of size p are * merged into runs of size 2p; within a merge, the gate distance k * halves from p down to 1. Every (p, k) pair is one layer of gates on * disjoint wires, so a whole layer could fire in parallel, and the * schedule depends only on n, never on the data. n must be a power of * two between minSize and maxSize. * * Time: O(n log² n) comparators, O(log² n) depth in parallel. Space: O(1) extra. */export class SortingNetwork implements SortAlgorithm {  readonly name = "sorting-network";  readonly minSize = 4;  readonly maxSize = 32;  constructor(private readonly tracer?: Tracer) {}  sort(input: readonly number[]): number[] {    const a = [...input];    const array = [...input];    const n = a.length;    const n = array.length;    if (!this.supports(n)) {      throw new RangeError(`n must be a power of two from 4 to 32, got ${n}`);    }    for (let p = 1; p < n; p *= 2) {    for (let runSize = 1; runSize < n; runSize *= 2) {      for (let k = p; k >= 1; k = Math.floor(k / 2)) {      for (let stride = runSize; stride >= 1; stride = Math.floor(stride / 2)) {        // ▸ the next layer of gates, all on disjoint wires        this.tracer?.emit("layer", { k, p, array: [...a] });        this.tracer?.emit("layer", { stride, runSize, array: [...array] });        for (let j = k % p; j + k < n; j += 2 * k) {        for (let j = stride % runSize; j + stride < n; j += 2 * stride) {          for (let i = 0; i < k; i++) {          for (let i = 0; i < stride; i++) {            const lo = i + j;            const hi = i + j + k;            const hi = i + j + stride;            // Gates never cross a 2p block: those wires merge later.            if (Math.floor(lo / (2 * p)) !== Math.floor(hi / (2 * p))) continue;            if (Math.floor(lo / (2 * runSize)) !== Math.floor(hi / (2 * runSize))) continue;            // ▸ a gate looks at its two wires            this.tracer?.emit("compare", { i: lo, j: hi, k, p, array: [...a] });            this.tracer?.emit("compare", { i: lo, j: hi, stride, runSize, array: [...array] });            if (a[lo]! > a[hi]!) {            if (array[lo]! > array[hi]!) {              // ▸ the lower wire holds the bigger value, exchange them              this.tracer?.emit("swap", { i: lo, j: hi, k, p, array: [...a] });              this.tracer?.emit("swap", { i: lo, j: hi, stride, runSize, array: [...array] });              const held = a[lo]!;              const held = array[lo]!;              a[lo] = a[hi]!;              array[lo] = array[hi]!;              a[hi] = held;              array[hi] = held;            }          }        }      }    }    return a;    return array;  }  /** The network exists only for powers of two within the supported span. */  private supports(n: number): boolean {    return n >= this.minSize && n <= this.maxSize && (n & (n - 1)) === 0;  }}

The array sits on 16 wires. The gates that follow are fixed by that count alone: play to watch them fire in their set order.

import type { Tracer } from "../trace";import type { SortAlgorithm } from "./sort-algorithm";/** * Batcher's odd-even merge sort as a sorting network: a fixed schedule * of compare-exchange gates between wire positions. Runs of size p are * merged into runs of size 2p; within a merge, the gate distance k * halves from p down to 1. Every (p, k) pair is one layer of gates on * disjoint wires, so a whole layer could fire in parallel, and the * schedule depends only on n, never on the data. n must be a power of * two between minSize and maxSize. * * Time: O(n log² n) comparators, O(log² n) depth in parallel. Space: O(1) extra. */export class SortingNetwork implements SortAlgorithm { readonly name = "sorting-network"; readonly minSize = 4; readonly maxSize = 32; constructor(private readonly tracer?: Tracer) {} sort(input: readonly number[]): number[] { const a = [...input]; const array = [...input]; const n = a.length; const n = array.length; if (!this.supports(n)) { throw new RangeError(`n must be a power of two from 4 to 32, got ${n}`); } for (let p = 1; p < n; p *= 2) { for (let runSize = 1; runSize < n; runSize *= 2) { for (let k = p; k >= 1; k = Math.floor(k / 2)) { for (let stride = runSize; stride >= 1; stride = Math.floor(stride / 2)) { // ▸ the next layer of gates, all on disjoint wires this.tracer?.emit("layer", { k, p, array: [...a] }); this.tracer?.emit("layer", { stride, runSize, array: [...array] }); for (let j = k % p; j + k < n; j += 2 * k) { for (let j = stride % runSize; j + stride < n; j += 2 * stride) { for (let i = 0; i < k; i++) { for (let i = 0; i < stride; i++) { const lo = i + j; const hi = i + j + k; const hi = i + j + stride; // Gates never cross a 2p block: those wires merge later. if (Math.floor(lo / (2 * p)) !== Math.floor(hi / (2 * p))) continue; if (Math.floor(lo / (2 * runSize)) !== Math.floor(hi / (2 * runSize))) continue; // ▸ a gate looks at its two wires this.tracer?.emit("compare", { i: lo, j: hi, k, p, array: [...a] }); this.tracer?.emit("compare", { i: lo, j: hi, stride, runSize, array: [...array] }); if (a[lo]! > a[hi]!) { if (array[lo]! > array[hi]!) { // ▸ the lower wire holds the bigger value, exchange them this.tracer?.emit("swap", { i: lo, j: hi, k, p, array: [...a] }); this.tracer?.emit("swap", { i: lo, j: hi, stride, runSize, array: [...array] }); const held = a[lo]!; const held = array[lo]!; a[lo] = a[hi]!; array[lo] = array[hi]!; a[hi] = held; array[hi] = held; } } } } } return a; return array; } /** The network exists only for powers of two within the supported span. */ private supports(n: number): boolean { return n >= this.minSize && n <= this.maxSize && (n & (n - 1)) === 0; }}