Sorting
The permutations that sorting machines sort: stacks, queues, pop-stacks and deques, alone, in series or in parallel, and sorting maps such as West's stack-sorting map and bubble sort. Type a permutation to see which machines sort it, watch them at work, see where it sits among the classes, and how each specification builds it.
The hierarchy of classes
Each line goes up from a set to a larger one. Between two classes the inclusion comes from their bases, and with a set from a theorem. Hover over a line to see where it comes from. A machine sorts w when it writes 1, 2, …, n, reading w from left to right.
Test a permutation
One-line notation, like 41325. For length 10 or more, put a dot between the entries, like 4.5.6.7.8.9.10.1.2.3 (spaces work too).
Watch a machine sort w
The entries of w wait on the right, pass through the machine's stacks, queues and pop-stacks below the track, and arrive on the left, as in Knuth's picture of a stack as a railway siding. A machine with choices sorts w when some sequence of moves does: the page finds one, or shows the attempt that gets furthest. The arrow keys step and the space bar plays.
How w lives in the specification
Compare two sets
Is one inside the other? If it is, why. If it is not, the smallest permutation that shows it, in the one and not in the other: the first of the shortest length, in lexicographic order, among all permutations up to length 8. Every two of the sets have one or the other.
All pairs at a glance
Row A, column B: ⊆ when A is inside B, and otherwise the length of the smallest permutation in A and not in B. Click a cell to compare the two.
The classes and sets
A class PermPAL has gets a short card with a link. The others get a full card: the classes with no specification yet, and the sets that no finite basis describes. Each card names the machines that sort exactly its permutations, and its buttons play them on w.