Re:Skylinesort
by daniel-cussen on Thursday March 19, 2020 @05:00PM
(#22631688)
Yes, 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.
OK, 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).
Re:Skylinesort
by daniel-cussen on Friday March 20, 2020 @10:56PM
(#22643931)
I 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.
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.