[sfink]

Why O(n log n)? I guess I thought that mapping a coordinate to its distance from the start of a space filling curve would be a constant time operation, or rather, it would only be proportional to the number of bits in your coordinate system which is usually ignored in combinatorial analysis.

Because once you have that, you just need to sort simple integers, which you can do in linear time with a radix sort. (Again ignoring bit lengths.)

What am I missing?