News for hackers. Stuff that matters.
Re:Lampsort: Leslie Lamport's Non-recursive Quicksort by Cushman on Sunday December 07, 2014 @01:45PM (#8713093)
If I understand the argument, the use of a set rather than a stack encodes the observation that the order of execution of adjacent partition operations isn't important. That ordering is information you don't have to store, meaning you can choose any set-like data structure, and being able to choose your access is theoretically useful: For example, by following a rule like "partition the smallest interval first", you could keep the set size ("depth") to a minimum. (That might be handy due to random pivot choice?) You don't have the freedom to choose that in a stack-backed implementation, whether recursive or "non".

So it is reasonable to argue this is a more abstract, "fundamental" implementation of the sort. Intuitively, I'm not sure it's that different from "remov[ing] the recursion, for example by making the stack explicit", then removing the stack, but it's sure interesting.

Edit: See https://news.ycombinator.com/item?id=8713160 for more context; this is correct, but the point is not really about how the code works.

Re:Lampsort: Leslie Lamport's Non-recursive Quicksort by tedunangst on Sunday December 07, 2014 @03:20PM (#8713413)
"Smallest interval first" is exactly what naive recursion gives you.
Re:Lampsort: Leslie Lamport's Non-recursive Quicksort by TheLoneWolfling on Sunday December 07, 2014 @04:39PM (#8713667)
Not quite.

Naive recursion doesn't generally change the order between the two subproblems at a single stage. It's generally just sort(first half), sort(second half).

Think of the case of a really bad pivot as the first choice - say, the second-highest element. Naive recursion generally will recurse on the lower chunk first, whereas smallest chunk first will recurse on the higher chunk.

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.

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.