3 ms·
Closely related is pattern defeating quicksort ( https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort ), which adapts quicksort to take advantage of
by CJefferson 4y ago
Closely related is pattern defeating quicksort ( https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort ), which adapts quicksort to take advantage of sorted runs. I've adapted a few quicksorts to pdqsort and seen good speedups (as people were often sorting partially sorted data)
Basically: Timsort is to mergesort as pdqsort is to quicksort
- masklinn 4y ago> Timsort is to mergesort as pdqsort is to quicksort It’s the other way around, since timsort is a decade older than pdqsort.
- dragonwriter 4y agoAge has nothing to do with the accuracy of the analogy, which says nothing about the temporal relationship between timsort and pdqsort.
- BizarroLand 4y agoMy favorite oddball sorting algorithm is StalinSort. It runs in (O)1 time, making it probably the fastest sorting algorithm in the world. It iterates through the list, and deletes every item in the list that isn't ordered. The remaining list is therefore automatically ordered.
- magicalhippo 4y agoHadn't heard of that one, and looking it up I stumbled upon this[1] delightful collection of esoteric sorting algorithms. Perfect for a Friday evening... [1]: https://towardsdatascience.com/esoteric-sort-algorithms-and-how-to-implement-them-in-python-96c663fa6ae5 https://towardsdatascience.com/esoteric-sort-algorithms-and-...
- reidjs 4y agoIf it iterates over every item in the list then it’s O(n) time
- drexlspivey 4y agoJust delete the whole list
- willcipriano 4y agoWhy would they ask to sort it if it is already sorted? Deleting the list resolves any out of order items.
- BizarroLand 4y agoBLARG. I knew that but I second guessed myself into getting it wrong. Thanks for the clarification.
- BizarroLand 4y agoI guess you could make a Blitzkrieg multithreaded variation, then it would run in O(Log N) time.
- deleted 4y ago[deleted]