34 ms·
Fair point. I assume you get a reasonable pivot. Recursing on one of the two halves of the "current" partition is the cache friendliest option. Smallest interv
by tedunangst 12y ago
Fair point. I assume you get a reasonable pivot.
Recursing on one of the two halves of the "current" partition is the cache friendliest option. Smallest interval will guarantee this by induction, I think, but I've never heard that the size of the stack is really a problem in quicksort. If you continuously partition out only a single element, your runtime is going to suck, even if you "sort" those elements first.
- TheLoneWolfling 12y ago> I've never heard that the size of the stack is really a problem in quicksort Naive quicksort tends to, in pathological cases, run out of stack space as opposed to having performance issues. Smallest-interval ends up with a strict upper limit of O(log n) elements in the running set, as opposed to O(n) for naive quicksort. This can be useful.