Hilbert Sort

Placing elements in databases according to a numeric key not only simplifies searching for a specific element, but also enables more efficient use of the CPU cache: any contiguous memory segment stores elements with close key values. This is particularly useful, for example, when accessing all elements whose keys lie within a given range.

The situation becomes more complicated if the keys represent points on a two-dimensional grid, as is the case, for instance, in GPS navigation systems. If the points $(x,y)$ are sorted first by $x$ and then by $y$, then elements located close to each other in memory will have identical $x$ values but may differ significantly in $y$. At the same time, points with equal $y$ values may be located far apart on the plane. To better preserve spatial locality, the data can be ordered along a continuous space-filling curve.

Consider one such curve, known as the Hilbert curve. It starts at the point $(0,0)$ and ends at $(S,0)$, visiting all points of the square with corners at $(0,0)$ and (S, S). The curve is defined recursively as follows: divide the square into four equal parts with a common point at (S/2, S/2), and recursively fill each part with a scaled and appropriately rotated copy of the full Hilbert curve.

First, the lower-left square is filled with a curve going from $(0,0)$ to (0, S/2). Then the upper-left square is filled from (0, S/2) to (S/2, S/2). Next, the upper-right square is filled from (S/2, S/2) to (S, S/2). Finally, the lower-right square is filled from (S, S/2) to $(S,0)$.

On the other hand, the Hilbert curve can also be viewed as the limit of a sequence of polygonal lines, the first few of which are shown in the figure.

You are given a set of points that must be sorted according to their order of traversal along the Hilbert curve. Although the curve intersects itself infinitely many times (for example, at the point (S/2, S/2)), the condition that $S$ is odd guarantees that every integer point is visited exactly once.