Comment by nightcracker | Hacker News Reader

Comment by nightcracker | Hacker News Reader

Parent Full thread

You might be interested in my new sorting algorithm, Pattern-defeating Quicksort (pdqsort): https://github.com/orlp/pdqsort

It's fully deterministic, as fast as Quicksort in the average case, O(n) in the best case (all equal, but it scales smoothly as the number of unique elements decreases), is optimized for common inputs like ascending/descending (both O(n)) and uses a novel idea of guaranteeing O(n log n) worst case, that guarantees the worst case is no slower than three times the average case, assuming heapsort is twice as slow as Quicksort.

I'm still tweaking the final details and working on the paper, so it's not ready for a full release yet, but a sneak peek here and there is nice :)

This is a benchmark comparing pdqsort against introsort (std::sort), heap sort and timsort: http://i.imgur.com/TSvXnG5.png .

Which timsort implementation did you compare to? (your profile.cpp on github doesn't include it).

Heapsort implementation vary widely in their cache coherence. The vast majority are extremely simple but result in essentially complete incoherence. I was once able to speed a heapsort about 2x by rearranging the scan order into a cache-oblivious one (Mostly the heap building part; I'm not aware of a way to make the extraction part cache-friendy).

Heapsorts, quicksorts and bubble sorts have the ability to sort just the "top-n" and stop there (unlike mergesort), which is often useful, and a significat speed up (goes from nlog(n) to n+mlog(n) to get top m, or from n^2 to n times m for bubble sort) - I wish library routines actually provided that as part of a standard interface. Perhaps you could be the torchbearer in your publication?

Personally, I think just about every standard library except APL/J/K got sorting wrong. The primary sort operation should be "compute stable ordering permutation", with "sort this array" (basically only available operation in most libraries) being at most a shortcut when you don't care about the permutation.

I'm sorry, the profiling code for timsort wasn't included in my remote repository yet. I profiled against https://github.com/gfx/cpp-TimSort .

Also, C++ has always had the "top-n" interface called partial sort: http://en.cppreference.com/w/cpp/algorithm/partial_sort .

I wrote a partial quicksort for Newzbin - once I saw how simple it was to add I was surprised it wasn't more widespread: https://github.com/Freaky/pqsort

>pdqsort

Reply on news.ycombinator.com