Sorting

Thirty eight algorithms, every comparison and every write recorded as it happens, then played back at whatever speed you like. Scrub it, step through one comparison at a time, race six on the same array, or write a sort of your own in the box at the bottom.

0 of 0

Drag the long bar to go anywhere in the recorded run.

being touched this instant settled for good not there yet the pivot, and the edges of the range it is working on

Algorithm

Starting order Draw it as

Elements 180 how many things to sort

Whole run in 12s

Sound on the mute above the panel is the whole site

Seed the same seed always gives the same array

Sound, look, and typing your own array

Tone

Pitch range 2.6 octaves how far the tone travels from bottom to top

Contrast normal how dark the ones it has not reached sit

Glow on the column of light where it is working

Show the working buffer under the array Show the pivot and range markers

Your own array numbers with anything you like between them, then pick "the one you typed in" above

Write a sort of your own

Write the body of a sort in JavaScript. You get n, the number of elements, and R, the same recorder every algorithm above is written against. You never see the values: you ask R to compare two positions and it tells you which way round they are, and you ask it to move things. It runs in a worker, so a loop that never ends stops the worker rather than the page.

What R gives you

R.cmp(i, j): compare the two positions. Negative if i belongs before j, zero if they match, positive otherwise. Counts one comparison.
R.swap(i, j): exchange them. Counts one swap and two writes.
R.move(dst, src): copy src over dst. One write.
R.hold(i): pick position i up into the one spare register.
R.drop(i): put the register down at position i. One write.
R.cmpH(i): compare position i against whatever is in the register.
R.exch(i): swap the register with position i in one move. One write.
R.read(i): the actual value at i, for a sort that does not compare, like a radix pass. Counts a read.
R.range(): the smallest and largest values, as a pair. Costs n reads.
R.needAux(m): ask for m cells of scratch space before you use any of it.
R.toAux(k, i): copy position i into scratch cell k. R.frAux(i, k) brings it back.
R.cmpAux(i, k): compare position i with scratch cell k. R.cmpAA(k, l) compares two scratch cells.
R.holdAux(k): and R.dropAux(k), the register again but for scratch. R.auxMove(d, s) is both at once.
R.done(i): say that position i is now final, so it draws as settled. R.doneRange(lo, hi) for a stretch.
R.mark(slot, i): put a named marker at a position. Slots: 0 pivot, 1 low, 2 high, 3 middle, 4 heap, 5 second pivot, 6 sorted so far, 7 current.
R.mem(cells): say how much extra memory you are using at this moment, for the readout.
R.buckets(k): declare k buckets, then R.bump(b) each time one gains an item, and the histogram appears under the picture.
R.net(i, j): record that a comparator joined those two wires, for the network drawing.
R.rnd(): a random number between nought and one, from the run's seed, so the same seed gives the same run.

Nothing else touches the array, and every built in sort here is under the same restriction. That is what the stability check below rests on.

space play and pause · ← → one step, with shift for a hundred · R a new array · F fullscreen. A race is settled by work done, not by the clock. The sort time in the readout is measured with the recorder off, so it is the speed of one page in one tab rather than the speed of the algorithm.