可以对抗输入数据模式的排序算法。

quick sort 在输入数据接近有序的情况下，效率不高。

Pattern-defeating quicksort (pdqsort) is a novel sorting algorithm that combines the fast average case of randomized quicksort with the fast worst case of heapsort, while achieving linear time on inputs with certain patterns. pdqsort is an extension and improvement of David Mussers introsort. All code is available for free under the zlib license.

pdqsort 结合了随机化的 quicksort 的快速的平均性能，和 heapsort 在最坏情况下的性能，并且在某些特定的输入模式下，可以实现线性的性能。 pdqsort 是 David Mussers 的 introsort 的一个扩展。

https://github.com/orlp/pdqsort

Single Thread Algorithms This table provides a brief description of the single thread algorithms of the library.

ClickHouse/contrib/pdqsort/

https://www.boost.org/doc/libs/1_67_0/libs/sort/doc/html/sort/single_thread.html

Algorithm Stable Additional memory Best, average, and worst case method
spreadsort no key_length N, Nsqrt(LogN), min(NlogN, Nkey_length) Hybrid radix sort
pdqsort no Log N N, NLogN, NLogN Comparison operator
spinsort yes N / 2 N, NLogN, NLogN Comparison operator
flat_stable_sort yes size of the data / 256 + 8K N, NLogN, NLogN Comparison operator
  • spreadsort is an extremely fast hybrid radix sort algorithm, designed and developed by Steven Ross.
  • pdqsort is a improvement of the quick sort algorithm, designed and developed by Orson Peters.
  • spinsort is a stable sort that is fast with random or nearly sorted data, designed and developed by Francisco Tapia.
  • flat_stable_sort is a stable sort that uses very little additional memory (around 1% of the size of the data), providing 80% - 90% of the speed of spinsort, designed and developed by Francisco Tapia.