Hacker News Reader

Comment by daniel-cussen | Hacker News Reader

Skylinesort is a novel sorting algorithm that sorts integer keys. It outperforms current sorting algorithms when keys are clustered (not uniformly randomly distributed). I showed it to some profs at Stanford, and might publish it formally.

It sorts in time O(ku-ulog(u)+n), where k is the number of bits in each key, u is the number of unique elements, and n is the total number of elements.

View on HN

I am fairly certain this is the fastest method available https://sorting.cr.yp.to/index.html

That algo is fast as hell, that much is true.

I have not made SIMD optimizations, which djbsort includes, and skylinesort does not require pre-computing the merging network, or padding the array to that size. This works great for crypto where array sizes are known ahead of time and generally always the same, but not all use cases are like this.

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.

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).

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.

How does that compare with Radix sort? Isn't Radix O(kn)? I guess Skyline would be better if the number of unique elements are low?

Skylinesort appears to beat radix sort when the data is clustered, as it caches better, which is especially true when the number of unique elements is low.

The other thing about it that's better is that Skylinesort is the only sorting algorithm that is downward-concave, i.e. it takes less time to sort a list of size a (keeping clustering constant) than it takes to sort two lists of size a/2. In other words, it shows economies of scale. It has been a long-remarked paradox that sorting algorithms take longer per element when there's more elements.

I haven’t read this in detail, but a few things stand out. In the write up, you say it compares better than bitwise radix sort. You need to compare against an optimized byte-wise radix sort which is by far the fastest sort for decent sized arrays of integers. The second claim that skyline sort somehow sorts an array of size a faster than two arrays of size n does not make sense. That implies that the time per element goes to zero as the size goes to infinity. That would be faster than O(n), which is what radix sort is, i.e. constant time per element for larger arrays.

It sounds like this is just a variation of counting sort or bucket sort optimized for a small number of unique values.

I know I need to compare it head to head against bytewise radix sort. I might do that and get back with the results. In the meantime, let me clarify. EDIT: Blas Mena and I did test it against radix sort, you can find it https://github.com/daniel-cussen/skylinesort/blob/master/src..., it tests with 4-bit radix sort and radix sort comes out 3% slower.

When I say that it can sort an array of size 2n faster than two arrays of size n it is because if you plot the asymptotic time, you find it's second derivative is negative (concave-up). This is because of the subtraction in the asymptotic time, O(k u - u log u + n). A Stanford professor was reluctant to accept an asymptotic time with a subtraction in it, but I explained it was really the logarithm of a division, ku-ulogu was actually u log(K/u) where K is 2^k, the total number of elements in the empty auxiliary array. log(K / u) is the same as log K - log u and log(K)=k, so you end up with k u - u log u, which has a negative second derivative when k is fixed.

When log u = k, skylinesort does indeed run in linear time, but it runs slower that linear time before that, and log u is never greater than k, by definition.

Daniel also addressed this some, but I want to highlight that sorting one array of size 2n faster than two arrays of size n does not imply per element time decreasing to zero. E.g. if the runtime were n-2^(-n) you would have that property even though the per element runtime tends toward 1.

<rant> That kind of phenomenon (reading too far into an infinite process) is ubiquitous once you start noticing it. Infinitely many universes don't imply the existence of every possible universe (if you subscribe to such theories), pie having infinitely many digits doesn't imply that it encodes every possible message somewhere in those digits (most real numbers have that property, but iirc it's still an open question for pi), and so on. </rant>

Why make a website and a domain name before getting peer review to check for mistakes?

I did a fair amount of that, but there was a lack of interest because it's just a sorting algorithm. Sorting is considered dead as a field, it's basically solved.

Since when has being a mistake prevented people from making a website and a domain name (and acquiring funding)?

Reply on news.ycombinator.com