4 ms·

Thanks for sharing this. Often sorting algorithms in practice end up being glommed into a Swiss Army knife style sort function to avoid pathological cases. E.g

Thanks for sharing this. Often sorting algorithms in practice end up being glommed into a Swiss Army knife style sort function to avoid pathological cases. E.g for smaller inputs just use insertion sort, but swap to a different sort of you know the size, etc. it’s pretty common in standard libraries (I think). So I am curious: are any pathological cases for skyline sort?

cormacrelf 7y ago
Well, it requires a ton of (virtual) memory for [0, 1e9], so much you can't do it on 32-bit machines. If you can figure out that a particular quicksort/etc subproblem has a pretty small abs(max-min), then cool, go for it, but try to reuse the allocations for other subproblems. With this memory issue, it's not a general purpose sort, nor does it have subproblems that you can defer to other sorts, so you wouldn't be able to use it as a default in those "glomsorts" anyway. So plugging pathological gaps is a bit irrelevant.
- daniel-cussen 7y ago
  It definitely requires a ton of virtual memory, and yes, you can't do 32-bit word sorting on 32-bit machines. There's actually a use case involving 24-bit words where the number of occurrences of each word doesn't matter, and where they necessarily start to cluster after each iteration. So there is a use case (I might add it's tailor-made for this use-case). But you can still e.g. sort database keys which might only have a 26-bit maximum, and it'll take advantage of any clustering that exists in the data, like if in a log you get some customers appearing more often than others, or more frequently in streaks. It also works great when your data is in ranges and you don't want to manually account for this: this will skip that entire empty range in logarithmic time. (Example, all your keys are between 1000-1100 and 5000-6000. The empty range 1100-4999 will be traversed in like 12 steps.)
daniel-cussen 7y ago
The pathological case for skylinesort is the optimal case for quicksort: uniformly randomly distributed data. In this case skylinesort is 3-4x slower than quicksort. It's still not like the pathological case of quicksort, which takes quadratic time: it's an effectively log-linear worst case. My advice is to use skylinesort when you have or can have tons of empty memory and have clustered data. Clustered means there's repetition of data points or they are in some ranges more than others. But in practice whenever your data isn't uniformly randomly distributed, skylinesort is better.

cormacrelf 7y ago

Well, it requires a ton of (virtual) memory for [0, 1e9], so much you can't do it on 32-bit machines. If you can figure out that a particular quicksort/etc subproblem has a pretty small abs(max-min), then cool, go for it, but try to reuse the allocations for other subproblems. With this memory issue, it's not a general purpose sort, nor does it have subproblems that you can defer to other sorts, so you wouldn't be able to use it as a default in those "glomsorts" anyway. So plugging pathological gaps is a bit irrelevant.

daniel-cussen 7y ago
It definitely requires a ton of virtual memory, and yes, you can't do 32-bit word sorting on 32-bit machines. There's actually a use case involving 24-bit words where the number of occurrences of each word doesn't matter, and where they necessarily start to cluster after each iteration. So there is a use case (I might add it's tailor-made for this use-case). But you can still e.g. sort database keys which might only have a 26-bit maximum, and it'll take advantage of any clustering that exists in the data, like if in a log you get some customers appearing more often than others, or more frequently in streaks. It also works great when your data is in ranges and you don't want to manually account for this: this will skip that entire empty range in logarithmic time. (Example, all your keys are between 1000-1100 and 5000-6000. The empty range 1100-4999 will be traversed in like 12 steps.)

daniel-cussen 7y ago

The pathological case for skylinesort is the optimal case for quicksort: uniformly randomly distributed data. In this case skylinesort is 3-4x slower than quicksort. It's still not like the pathological case of quicksort, which takes quadratic time: it's an effectively log-linear worst case. My advice is to use skylinesort when you have or can have tons of empty memory and have clustered data. Clustered means there's repetition of data points or they are in some ranges more than others. But in practice whenever your data isn't uniformly randomly distributed, skylinesort is better.