3 ms·
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 compar
by Scea91 11y ago
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.
- amelius 11y ago> 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).
- Scea91 11y agoI 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.
- larshagencpp 11y agoHow 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.
- Scea91 11y agoThe items are sorted after each insertion.
- larshagencpp 11y agoYes, 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.
- cyphar 11y agoWhy 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.
- bwhmather 11y agoThe 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.