Skip to content
Computational Lab.

Sorting

Six strategies for imposing order.

Beginner / sorting / comparison

Bubble, selection, insertion, merge, quick, and heap sort arrange the same array under the same rules. Watching them turns big-O notation into something you can see: how many comparisons each strategy pays, how far its writes reach, and where the quadratic methods fall apart.

Tagged: comparison sort, complexity, swap count

Live simulation

Each step performs a fixed number of real comparison and write operations.

Speed

Each step performs a fixed number of real comparison and write operations.

Mathematics

Every comparison sort pays for order with yes/no questions. Information theory sets the floor: distinguishing one of n! permutations takes at least log₂(n!) comparisons, which Stirling approximates as n log₂ n − 1.44n.

lower bound: comparisons ≥ log₂(n!) ≈ n log₂ n − 1.44 n

bubble / insertion / selection: O(n²) worst case

merge / heap: O(n log n) worst case; quick: O(n log n) expected, O(n²) worst

The counters in the metrics strip are incremented by the algorithm itself, one per operation, so the asymptotics are observable rather than asserted. Watch insertion sort on a nearly sorted array to see its O(n) best case, then randomize to see the quadratic methods fall behind.

How it works

Each algorithm is written as a generator that yields one displayable operation at a time: a comparison (two indices) or a write (index and value). A driver consumes a fixed number of operations per tick, so stepping always advances the real computation and pausing changes nothing.

The array is a seeded Fisher-Yates shuffle of 1..n, so reset reproduces the exact same input for the same seed. Merge sort writes through an auxiliary buffer; quicksort uses median-of-three pivot selection with an explicit stack instead of recursion.

Implementation

src/engine/experiments/sorting.ts · 292 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, ThemeColors } from "../core/types";
3
4type Op = { t: "cmp"; i: number; j: number } | { t: "set"; i: number; v: number };
5
6interface SortContext {
7 arr: number[];
8 aux: number[];
9 comparisons: number;
10 writes: number;
11}
12
13/**
14 * Six comparison sorts driven as explicit operation generators, so "step"
15 * advances a fixed number of real operations per tick. Correctness is
16 * unit-tested for every algorithm.
17 */
18export class SortingExperiment extends BaseExperiment {
19 readonly id = "sorting";
20
21 private items: number[] = [];
22 private ctx: SortContext = { arr: [], aux: [], comparisons: 0, writes: 0 };
23 private generator: Generator<Op> | null = null;
24 private done = false;
25 private comparedIndex = -1;
26 private comparedAgainst = -1;
27 private lastPivot = 0;
28
29 protected params(): ParameterDef[] {
30 return [
31 { key: "size", label: "Array size", min: 16, max: 240, step: 8, defaultValue: 96 },
32 { key: "ops", label: "Operations per tick", min: 1, max: 60, step: 1, defaultValue: 4 },
33 {
34 key: "algorithm",
35 label: "Algorithm",
36 options: [
37 { value: "bubble", label: "Bubble sort" },
38 { value: "selection", label: "Selection sort" },
39 { value: "insertion", label: "Insertion sort" },
40 { value: "merge", label: "Merge sort" },
41 { value: "quick", label: "Quick sort" },
42 { value: "heap", label: "Heap sort" },
43 ],
44 defaultValue: "quick",
45 },
46 ];
47 }
48
49 protected onReset(): void {
50 const size = this.num("size");
51 this.items = new Array(size);
52 for (let i = 0; i < size; i++) this.items[i] = i + 1;
53 // Fisher-Yates with the seeded RNG: deterministic shuffle per seed.
54 for (let i = size - 1; i > 0; i--) {
55 const j = Math.floor(this.rng() * (i + 1));
56 const tmp = this.items[i];
57 this.items[i] = this.items[j];
58 this.items[j] = tmp;
59 }
60 this.ctx = { arr: this.items, aux: new Array(size), comparisons: 0, writes: 0 };
61 this.generator = this.buildGenerator(this.ctx, this.str("algorithm"));
62 this.done = false;
63 this.comparedIndex = -1;
64 this.comparedAgainst = -1;
65 }
66
67 protected onParameterChange(key: string): void {
68 if (key === "size" || key === "algorithm") this.reset();
69 }
70
71 private *compare(ctx: SortContext, i: number, j: number): Generator<Op> {
72 ctx.comparisons += 1;
73 yield { t: "cmp", i, j };
74 }
75
76 private *writeOp(ctx: SortContext, i: number, v: number): Generator<Op> {
77 ctx.writes += 1;
78 yield { t: "set", i, v };
79 }
80
81 private *swap(ctx: SortContext, i: number, j: number): Generator<Op> {
82 ctx.writes += 2;
83 const tmp = ctx.arr[i];
84 yield { t: "set", i, v: ctx.arr[j] };
85 yield { t: "set", i: j, v: tmp };
86 }
87
88 private *buildGenerator(ctx: SortContext, algorithm: string): Generator<Op> {
89 const n = ctx.arr.length;
90 switch (algorithm) {
91 case "bubble": {
92 for (let end = n - 1; end > 0; end--) {
93 let swapped = false;
94 for (let i = 0; i < end; i++) {
95 yield* this.compare(ctx, i, i + 1);
96 if (ctx.arr[i] > ctx.arr[i + 1]) {
97 yield* this.swap(ctx, i, i + 1);
98 swapped = true;
99 }
100 }
101 if (!swapped) return;
102 }
103 return;
104 }
105 case "selection": {
106 for (let i = 0; i < n - 1; i++) {
107 let min = i;
108 for (let j = i + 1; j < n; j++) {
109 yield* this.compare(ctx, j, min);
110 if (ctx.arr[j] < ctx.arr[min]) min = j;
111 }
112 if (min !== i) yield* this.swap(ctx, i, min);
113 }
114 return;
115 }
116 case "insertion": {
117 for (let i = 1; i < n; i++) {
118 const key = ctx.arr[i];
119 let j = i - 1;
120 while (j >= 0) {
121 yield* this.compare(ctx, j, j + 1);
122 if (ctx.arr[j] <= key) break;
123 yield* this.writeOp(ctx, j + 1, ctx.arr[j]);
124 j -= 1;
125 }
126 if (j + 1 !== i) yield* this.writeOp(ctx, j + 1, key);
127 }
128 return;
129 }
130 case "merge":
131 yield* this.mergeSort(ctx, 0, n - 1);
132 return;
133 case "quick": {
134 const stack: [number, number][] = [[0, n - 1]];
135 while (stack.length) {
136 const [lo, hi] = stack.pop()!;
137 if (lo >= hi) continue;
138 const pivotIndex = yield* this.partition(ctx, lo, hi);
139 stack.push([lo, pivotIndex - 1]);
140 stack.push([pivotIndex + 1, hi]);
141 }
142 return;
143 }
144 case "heap": {
145 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) yield* this.siftDown(ctx, i, n);
146 for (let end = n - 1; end > 0; end--) {
147 yield* this.swap(ctx, 0, end);
148 yield* this.siftDown(ctx, 0, end);
149 }
150 return;
151 }
152 default:
153 return;
154 }
155 }
156
157 private *partition(ctx: SortContext, lo: number, hi: number): Generator<Op, number> {
158 // Median-of-three pivot selection keeps the demo honest on sorted inputs.
159 const mid = (lo + hi) >> 1;
160 yield* this.compare(ctx, lo, mid);
161 if (ctx.arr[mid] < ctx.arr[lo]) yield* this.swap(ctx, mid, lo);
162 yield* this.compare(ctx, mid, hi);
163 if (ctx.arr[hi] < ctx.arr[mid]) yield* this.swap(ctx, mid, hi);
164 yield* this.compare(ctx, lo, mid);
165 if (ctx.arr[mid] < ctx.arr[lo]) yield* this.swap(ctx, mid, lo);
166 yield* this.swap(ctx, mid, hi);
167 const pivot = ctx.arr[hi];
168 let i = lo;
169 for (let j = lo; j < hi; j++) {
170 yield* this.compare(ctx, j, hi);
171 if (ctx.arr[j] < pivot) {
172 if (i !== j) yield* this.swap(ctx, i, j);
173 i += 1;
174 }
175 }
176 if (i !== hi) yield* this.swap(ctx, i, hi);
177 return i;
178 }
179
180 private *mergeSort(ctx: SortContext, lo: number, hi: number): Generator<Op> {
181 if (lo >= hi) return;
182 const mid = (lo + hi) >> 1;
183 yield* this.mergeSort(ctx, lo, mid);
184 yield* this.mergeSort(ctx, mid + 1, hi);
185 let i = lo;
186 let j = mid + 1;
187 let k = lo;
188 while (i <= mid && j <= hi) {
189 yield* this.compare(ctx, i, j);
190 ctx.aux[k++] = ctx.arr[i] <= ctx.arr[j] ? ctx.arr[i++] : ctx.arr[j++];
191 }
192 while (i <= mid) ctx.aux[k++] = ctx.arr[i++];
193 while (j <= hi) ctx.aux[k++] = ctx.arr[j++];
194 for (let t = lo; t <= hi; t++) {
195 if (ctx.arr[t] !== ctx.aux[t]) yield* this.writeOp(ctx, t, ctx.aux[t]);
196 }
197 }
198
199 private *siftDown(ctx: SortContext, root: number, end: number): Generator<Op> {
200 while (true) {
201 const left = root * 2 + 1;
202 const right = left + 1;
203 if (left >= end) return;
204 let largest = root;
205 yield* this.compare(ctx, left, largest);
206 if (ctx.arr[left] > ctx.arr[largest]) largest = left;
207 if (right < end) {
208 yield* this.compare(ctx, right, largest);
209 if (ctx.arr[right] > ctx.arr[largest]) largest = right;
210 }
211 if (largest === root) return;
212 yield* this.swap(ctx, root, largest);
213 root = largest;
214 }
215 }
216
217 protected onUpdate(): void {
218 if (this.done || !this.generator) return;
219 const opsPerTick = this.num("ops");
220 for (let i = 0; i < opsPerTick; i++) {
221 const op = this.generator.next();
222 if (op.done) {
223 this.done = true;
224 this.comparedIndex = -1;
225 this.comparedAgainst = -1;
226 break;
227 }
228 const value = op.value;
229 if (value.t === "cmp") {
230 this.comparedIndex = value.i;
231 this.comparedAgainst = value.j;
232 } else {
233 this.items[value.i] = value.v;
234 }
235 }
236 }
237
238 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
239 ctx.fillStyle = theme.bg;
240 ctx.fillRect(0, 0, this.width, this.height);
241 const n = this.items.length;
242 if (n === 0) return;
243 const gap = n > 160 ? 0 : Math.max(1, Math.floor(this.width / n / 8));
244 const barWidth = this.width / n - gap;
245 for (let i = 0; i < n; i++) {
246 const h = (this.items[i] / n) * (this.height - 8);
247 const x = i * (barWidth + gap);
248 let color = theme.fgSecondary;
249 if (this.done) color = theme.accent;
250 else if (i === this.comparedIndex) color = theme.accent;
251 else if (i === this.comparedAgainst) color = theme.accentStrong;
252 ctx.fillStyle = color;
253 ctx.fillRect(x, this.height - h, barWidth, h);
254 }
255 }
256
257 getMetrics() {
258 let orderedPairs = 0;
259 for (let i = 1; i < this.items.length; i++) {
260 if (this.items[i - 1] <= this.items[i]) orderedPairs += 1;
261 }
262 const orderPercent =
263 this.items.length > 1 ? (orderedPairs / (this.items.length - 1)) * 100 : 100;
264 return {
265 algorithm: this.labelFor(this.str("algorithm")),
266 comparisons: this.ctx.comparisons,
267 writes: this.ctx.writes,
268 order: `${orderPercent.toFixed(1)} %`,
269 status: this.done ? "Sorted" : "Running",
270 };
271 }
272
273 private labelFor(value: string): string {
274 const def = this.getParameters().find((p) => p.key === "algorithm");
275 if (def && "options" in def) {
276 return def.options.find((o) => o.value === value)?.label ?? value;
277 }
278 return value;
279 }
280
281 describe(): string {
282 if (this.done) {
283 return `Sorted with ${this.labelFor(this.str("algorithm"))} after ${this.ctx.comparisons.toLocaleString("en-US")} comparisons and ${this.ctx.writes.toLocaleString("en-US")} array writes.`;
284 }
285 return `${this.labelFor(this.str("algorithm"))} in progress: ${this.ctx.comparisons.toLocaleString("en-US")} comparisons so far.`;
286 }
287
288 entities(): number {
289 return this.items.length;
290 }
291}
292

Performance

Time per tick
One tick performs a fixed number of yielded operations
Space
O(n) values plus O(n) auxiliary for merge sort
Notes
Comparison counts are measured, not estimated: switch algorithms on the same seed and compare the totals.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.