4 ms·

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

You might be interested in my new sorting algorithm, Pattern-defeating Quicksort (pdqsort): https://github.com/orlp/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 http://i.imgur.com/TSvXnG5.png .

beagle3 12y ago
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.
- nightcracker 12y ago
  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 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 http://en.cppreference.com/w/cpp/algorithm/partial_sort .
- Freaky 12y ago
  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 https://github.com/Freaky/pqsort
qnaal 12y ago
>pdqsort

beagle3 12y ago

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.

nightcracker 12y ago
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 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 http://en.cppreference.com/w/cpp/algorithm/partial_sort .
Freaky 12y ago
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 https://github.com/Freaky/pqsort

qnaal 12y ago

>pdqsort