3 ms·
The insight I might have not made clear, is that if you have “this node and its children are already sorted” metadata, then it’s cheaper to check whether a give
by derefr 7y ago
The insight I might have not made clear, is that if you have “this node and its children are already sorted” metadata, then it’s cheaper to check whether a given (fine-grained) input chunk is already sorted—and if so, to directly construct a node from it—than it is to feed it blindly to the sorting algorithm.
If such a pre-check is in play, then the sorting algorithm itself will basically never have the sort of “runs” of sorted values that make some algorithms cheaper. Those “runs” were already plucked out and turned into nodes!