3 ms·
You seem to require the auxiliary array to be initialized to zero. This costs O(2^k). Second, consider this line. > Otherwise we keep traveling to the left un
by Veedrac 7y ago
You seem to require the auxiliary array to be initialized to zero. This costs O(2^k).
Second, consider this line.
> Otherwise we keep traveling to the left until we are able to make another leap.
Wouldn't sorting an array with the two elements 2^n and 2^(n+1)-1 require ~2^n repeats of this step? That's a second 2^k cost.
Overall this is just counting sort with skips, but for that I'd imagine it's cheaper to just use a bit array to track set elements, which also makes zeroing much faster.
- daniel-cussen 7y agoYes, the original auxiliary array has to start out being zero, but it is returned in that same state, so this algo can be run over and over again without ever having to reinitialize the entire array in O(2^k). When there's 2^n and 2^(n+1)-1, it takes n-2 steps to reach the former from the latter, not 2^n.
- Veedrac 7y agoOK, I got it after reading the code. It's a neat trick, but you never actually explain how it works (even the comment says ‘this part I'm confused about’ lol).
- daniel-cussen 7y agoI think I know what you mean. There is a step in the logic that, in a staircase metaphor, is uneven, it's a larger gap than the other steps, and also like a real staircase, you either make that step or you don't. I have yet to find a way to explain it. Personally, I can't always understand it, and don't know how I know it, and can't put my finger on what the leap is.