orlp / pdqsort

Pattern-defeating quicksort.
zlib License
2.37k stars 102 forks source link

Choose a small range for recursion. #23

Closed ikspress closed 1 year ago

ikspress commented 1 year ago

In libc++, they choose a smaller range for recursion, which reduces the recursion depth. This could be very useful?

orlp commented 1 year ago

This just unnecessarily introduces a branch. Pattern-defeating quicksort is already limited to O(log n) stack depth, which should avoid any stack overflow.