4 ms·

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 im

by Cushman 12y ago

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 https://news.ycombinator.com/item?id=8713160 for more context; this is correct, but the point is not really about how the code works.

tedunangst 12y ago
"Smallest interval first" is exactly what naive recursion gives you.
- TheLoneWolfling 12y ago
  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.
  - 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.

by Cushman 12y ago

tedunangst 12y ago

"Smallest interval first" is exactly what naive recursion gives you.

TheLoneWolfling 12y ago
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.
- 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.