Hacker GitHub

← All repos

orlp/pdqsort

View on GitHub ↗ ★ 2,511 C++

Pattern-defeating quicksort.

24 mentions on Hacker News by 13 people: 5 stories, 19 comments · first 2015-02-24 · latest 2023-10-10

Mentions per year 24 mentions · busiest year 2015 (6)
20082026
AllStoriesComments NewestTopOldest
  1. …0(n log k) for k unique values on average using only a single extra comparison per partitioning. https://github.com/orlp/pdqsort
    comment by orlp · 2023-05-07 · in Qsort.h – Quicksort as a C macro (2019)
  2. Closely related is pattern defeating quicksort ( 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…
    comment by CJefferson · 2022-07-29 · in Timsort (2019)
  3. …Direct link to the GitHub home of pdqsort (in C++), which has some performance comparisons: https://github.com/orlp/pdqsort
    comment by MaxBarraclough · 2022-04-21 · in Go will use pdqsort in next release
  4. …comparisons. It's also available in Boost.sort [4]. [1] https://arxiv.org/abs/1604.06697 [2] https://github.com/orlp/pdqsort [3] https://arxiv.org/abs/2106.05123 [4] https://www.boost.org/doc/libs/1_76_0/libs/sort/doc/html/sor...
    comment by nightcracker · 2021-07-18 · in Do Low-Level Optimizations Matter? (2020)
  5. …as likely to occur in real-world input. For me determinism was very important so I didn't do it in https://github.com/orlp/pdqsort , but note that the variant implemented in Rust uses non-deterministic swapping and thus it is impossible to…
    comment by nightcracker · 2021-07-10 · in Blitsort is an in-place stable adaptive rotate merge sort
  6. Just for fun, I added pdqsort to the benchmark: https://github.com/orlp/pdqsort Here are some of the results on an Ivy Bridge hackintosh: size, qsort, inline, sort, stable, pdqsort, radix7 1000, 88.0, 60.6, 31.2, 37.5, 24.6, 12.8 10000,…
    comment by SloopJon · 2021-01-15 · in Beating Up on Qsort (2019)
  7. Hoare partitioning can also be implemented in a branchless manner, my algorithm pdqsort does this: https://github.com/orlp/pdqsort
    comment by nightcracker · 2020-05-17 · in Lomuto's Comeback
  8. …Shameless self promotion, if you want a faster sorting implementation, check out pdqsort ( https://github.com/orlp/pdqsort ) which is almost twice as fast as libstdc++'s std::sort for randomly shuffled integers, and has all sorts of tricks…
    comment by nightcracker · 2020-02-14 · in Quadsort: a stable non-recursive merge sort
  9. …(sequential and parallel, disclaimer: the authors are my colleagues) or https://github.com/orlp/pdqsort (sequential)
    comment by lorenzhs · 2020-01-20 · in Why is quicksort better than other sorting algorithms in practice? (2013)
  10. FWIW, Rust uses Pattern-defeating quicksort for it's unstable sort. [1] https://github.com/orlp/pdqsort [2] https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...
    comment by cbarrick · 2019-10-09 · in Timsort, the Python sorting algorithm
  11. …advantage of being easier to implement (particularly if you already have a quicksort lying around). https://github.com/orlp/pdqsort Basically, timsort is to mergesort as pdqsort is to quicksort.
    comment by CJefferson · 2019-10-08 · in Timsort, the Python sorting algorithm
  12. …be biased, and are always controversial. If you have any further questions, feel free to ask. [1]: https://github.com/orlp/pdqsort [2]: https://github.com/skarupke/ska_sort
    comment by _hrfd · 2017-06-29 · in Pattern-defeating quicksort
  13. …a 512 length set. Just a thought. I'd love to see what G++ is able to hob-cobble together. [0] - https://github.com/orlp/pdqsort/blob/master/pdqsort.h#L227-L...
    comment by gravypod · 2016-12-31 · in Questions about Superoptimization
  14. …true. In state of the art implementations quicksort is implemented in a branchless fashion. See https://github.com/orlp/pdqsort for details (I'm the author of pdqsort, old username on HN). The trick is to first replace directly swapping…
    comment by nightcracker · 2016-12-31 · in Questions about Superoptimization
  15. …if Quicksort encounters such a partition? I'd strongly suggest you to read the readme I wrote for https://github.com/orlp/pdqsort , which explains in detail how I beat heapsort (and other sorting algorithms). It also shows how I prevent…
    comment by nightcracker · 2015-10-30 · in A Killer Adversary for Quicksort (1999) [pdf]
  16. …faster than heapsort - mainly due to cache effects. See pdqsort for examples (benchmarks included): https://github.com/orlp/pdqsort . It shows that on average it's twice as fast on the random input distribution.
    comment by nightcracker · 2015-10-30 · in A Killer Adversary for Quicksort (1999) [pdf]
  17. …note, I'm talking to the libc++ and libstdc++ developers about replacing introsort with pdqsort ( https://github.com/orlp/pdqsort ) as the implementation for std::sort. It solves the worst case in a subtly different (and potentially more…
    comment by nightcracker · 2015-10-30 · in A Killer Adversary for Quicksort (1999) [pdf]
  18. …sort to prevent Quicksort's worst case, like introsort or (shameless self promotion) pdqsort ( https://github.com/orlp/pdqsort ).
    comment by nightcracker · 2015-06-03 · in Typelevel quicksort in Scala
  19. 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…
    comment by nightcracker · 2015-02-24 · in Proving that Android’s, Java’s and Python’s sorting algorithm is broken