Re:Lampsort: Leslie Lamport's Non-recursive Quicksort
by TheLoneWolfling on Monday December 08, 2014 @06:58AM
(#8716010)
> 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.
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.