Fast incremental sort(larshagencpp.github.io)

57 pointsby ingvevor 10 Jahren10 comments

larshagencpp.github.io

http://larshagencpp.github.io/blog/2016/04/23/fast-incremental-sort

2 comments

Freakyvor 10 Jahren

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

CyberDildonicsvor 10 Jahren

Looks a lot like std::partition

Scea91vor 10 Jahren

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.

bwhmathervor 10 Jahren

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.

larshagencppvor 10 Jahren

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.

Scea91vor 10 Jahren

The items are sorted after each insertion.

larshagencppvor 10 Jahren

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.

cypharvor 10 Jahren

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.

ameliusvor 10 Jahren

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

Scea91vor 10 Jahren

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.