In 1D, sorting is trivial because scalar values have a total, unambiguous order. In 2D and higher dimensions, there is no single way to order points, and points can't all be compared >=/<= in a consistant way. Space-filling curves like Hilbert or Z-order curves still can order Nd points by mapping them to a 1D index, but flattening the space sacrifices much of the original geometric structure.
Recently, I’ve been thinking about partial orders for d-dimensional vectors. For vectors u and v, let denote u >=_k v if u_k >= v_k (comparing along the k-th coordinate axis only).
In 1D, a sorted array satisfies x[i+1] >= x[i]. Extending this naturally to a multi-indexed d-dimensional array x[i, j, k, ...], we can define a dataset as "cartesian sorted" if:
- x[i+1, j, k, ...] >=_1 x[i, j, k, ...] - x[i, j+1, k, ...] >=_2 x[i, j, k, ...] - ...and so on.
In other words, the array of multi indexes is sorted along every row, column, and slice under its corresponding coordinate projection.
What makes this definition interesting is that their exist a very simple algorithm to perform Nd sort in the "cartesian" sense. Just iterate: 1. Perform 1D sorts along every row (apply the permutation i' = sigma_jk(i) on the multi indexes that make all the rows sorted in the >=^1 sense. 2. Perform 1D sorts along every column. 3. Repeat across all dimensions until convergence.
While sorting along one axis can disrupt the order along another, the process is guaranteed to converge fast to a fully "cartesian sorted" state (I have a short proof if anyone is curious).
---
Questions for the HN Community:
1. Is there existing literature or a standard name for this approach? Searching for multi-dimensional sorting mostly yields spatial indexing, radix, or binning approaches, but maybe I missed something obvious ?
2. What are the fundamental limitations that make this approach less common in practice than space-filling curves or k-d trees, if they are some in your opinion ? I thought it would be commonly used already, but it doesn't seems to be a standard tool.
3. Has anyone experimented with similar (or maybe better) multi-index coordinate sorting techniques? I’d love to hear your thoughts or critiques on the concept.