News for hackers. Stuff that matters.

A comment on Lampsort: Leslie Lamport's Non-recursive Quicksort. Parent comment

Re:Lampsort: Leslie Lamport's Non-recursive Quicksort by tedunangst on Sunday December 07, 2014 @05:22PM (#8713824)
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.

[ Parent | on HN ]
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.

[ Parent | on HN ]