Fast incremental sort | Hacker News Reader

Fast incremental sort

larshagencpp.github.io

57 pointsingve10 comments

At Newzbin we used a simple partial quicksort for returning paginated results from our custom search engine - it worked really well for our needs.

It was implemented as a plain old C macro: https://github.com/Freaky/pqsort

Looks a lot like std::partition

Where is the comparison with some binary search tree such as RB tree? I wouldn't be surprised if the method in the article is faster but IMO it should be compared with RB tree or something similar.

Edit: My fault. I misunderstood the incremental sort problem.

The smoothsort variant of heap sort might be a better alternative. It can be implemented in-place like an ordinary heap sort, but unlike an ordinary heap sort the root will be at the end of the heap where you want the elements to end up when they've been popped. The whole array, including the fully sorted part, will remain a valid heap so you can continue to add new elements efficiently.

How would you use an RB tree to do incremental sorting? Wouldn't you have to insert all the elements into the tree up-front? That would certainly be slower, but maybe you mean something different.

The items are sorted after each insertion.

Yes, but the incrmental sorting problem requires that the k elements are not only sorted, but are the k first elements of the whole sequence of length N.

Why does that make a difference? Every insertion into an RB tree self-balances and sorts the elements. So if you sort the first k elements (insert them in the tree), sorting the next element is fairly cheap (log k). Maybe I'm misunderstanding what you mean.

> I wouldn't be surprised if the method in the article is faster

If that is true, then I suspect we can toss RB trees out of the window. When searching for a key inside a sorted collection, you could use binary search of complexity O(log N), which is the same complexity as searching in an RB tree. So if incremental sorting is faster than updating an RB tree, we wouldn't really need RB trees.

Of course there could be special circumstances that change this (for example large batches of inserts).

I wrote it mainly not to be so dismissive about the article because I haven't read it that carefully.

With that said trees are also build to support fast deletion so that is one extra requirement that is not needed for incremental sort, maybe opening a potential possibility for some speedup.

Reply on news.ycombinator.com