On one hand, amelius is right, there are already simple fast stable sorts using O(sqrt(n)) extra space and that should be okay for all practical purposes. (Though they aren't very well known, and inventing one will take you a week or two.) Allocating 30K elements to help sort a billion elements is no big deal, you don't need to squeeze further. My interest is more academic, how come the known O(1) solutions are so complex compared to O(sqrt(n)) and can they be simplified.