No arrays, but a grid
Sorting algorithms usually assume an array: numbered slots you can read and write at will. Befunge has no array type, but it does have something that can play the same role. The playfield is a grid of cells, and the get (g) and put (p) instructions read and write any cell by column and row. A row of cells can serve as an array. Slot 0 is the cell at column 0, slot 1 is column 1, and so on, in a row far from the code.
A stack is a poor sorting tool by itself. You can only reach the top item, so comparing two items that are not on top means taking items off and putting them somewhere else. Using cells this way is the same technique as grid variables, applied to many slots instead of one. The grid takes the place of random access, at the price of extra instructions for every access.
The basic step: compare and order two values
Most simple sorts, including bubble sort and insertion sort, are built from one operation: look at two values, and swap them if they are in the wrong order. Here is that operation as a complete program. It orders two example values, 7 and 3, and prints the smaller first. It stores the values in cells (0, 3) and (1, 3).
7313p03p03g13g`v
@.g30.g31_03g.13g.@It prints 3 7 .
Store. 73 pushes 7 and 3. Then 13p pushes 1 and 3 and puts the top value, 3, at column 1, row 3. 03p puts the next value, 7, at column 0, row 3. The stack is now empty and the cells hold the two numbers: slot 0 is 7 and slot 1 is 3.
Compare. 03g reads slot 0, 13g reads slot 1, and the backtick pushes 1 if the first is greater than the second, otherwise 0. Here 7 is greater than 3, so the result is 1. The v then turns the pointer down onto the horizontal-if (_) in the second row.
Branch. The horizontal-if pops the result. Zero sends the pointer east, where 03g.13g. prints slot 0 and then slot 1. A nonzero value sends the pointer west, where the cells (read right to left) are 1, 3, g, ., 0, 3, g, ., @. That prints slot 1 and then slot 0. In this run the result is 1, so the output is 3 then 7.
Try other pairs to confirm the other branch: with 3 and 7, or with equal values, the output is 3 7 and 5 5 respectively. Equal values go east, which is fine since they do not need swapping.
Notice that this version does not actually move the values in the cells. It just decides the print order. That is enough for two values, but a real sort must write the values back in order so that later steps see the sorted arrangement. A write-back adds p instructions on each branch, with the arithmetic to calculate the cell coordinates.
Scaling up: what a full sort needs
A bubble sort on n slots makes repeated passes. Each pass compares neighbors (slot 0 with slot 1, slot 1 with slot 2, and so on), swapping when out of order. After the first pass the largest value has reached the end, so each later pass can stop one slot earlier. The number of comparisons is at most n(n − 1) / 2 in the worst case:
| Slots | Comparisons (at most) |
|---|---|
| 3 | 3 |
| 4 | 6 |
| 5 | 10 |
| 8 | 28 |
For five numbers, ten compare-and-order steps is manageable. For a hundred it would be close to five thousand, and each step costs a dozen or so instructions, so the pointer would take a long path across the grid. The playfield also has a limited size (80 by 25 in the classic model), so a long list may not fit anyway.
A complete sort needs:
- A loop counter for the outer passes, kept in another cell or on the stack.
- An index for the position being compared, which is used to compute the coordinates for
gandp. - A swap that reads both cells, writes them back reversed, and does so with the index plus one for the neighbor.
- A stop condition, either a fixed number of passes or a pass with no swaps.
Every one of these items is bookkeeping that an array-based language handles with a few lines. Here, each is a short stretch of arithmetic and a handful of arrows, which is why even a short sort program sprawls over the grid.
Design choices that make it easier
- Keep the data in one row. If each slot is at (i, r) for a fixed r, a single index variable is enough to address any slot.
- Keep data away from code. Stored values overwrite whatever was in the cell. Choose a row below all your instructions.
- Know the number range. A cell holds an integer, and the limits depend on the interpreter, so very large numbers can behave differently. Reading a cell back with
ggives its integer value, which the dot instruction prints as a number. - Tiny lists. For a fixed small count, such as three or four values, a hard-wired sorting network is simpler: a fixed list of compare-and-order steps with no loop at all. A network for three values uses three compare-and-order steps: slots (0, 1), then (1, 2), then (0, 1) again.
What this says about memory models
The comparison between a stack and a grid shows up across esoteric languages. Brainfuck keeps a tape with a moving head, which is a one-dimensional cousin of the grid. Languages with only a stack have to simulate random access by popping and pushing. The differences between memory models decide how awkward even small tasks become, and sorting is one of the clearest tests of that. A tape versus grid comparison makes the cost difference concrete, and a good playfield data structure inside an interpreter is what keeps g and p cheap.
One more point: because code and data share the same grid, a careless p can change the program itself. Doing that on purpose is the idea behind self-modifying code, but in a sort it is usually an accident, and it is a common source of mysterious bugs. Speed matters little for lists this short, though interpreter performance becomes noticeable if you try a larger one.