Is iterative (stack based) quick sort faster than recursive?

Question

In various places I've seen claims that implementing quicksort using a stack is faster than using recursion. Is this true? I know compilers are often good at changing recursion into iterations, but the comments on the page linked to claim it is too complicated to optimize.

What other optimizations exist for quicksort?

Here are some places I red that itterative implementations are better than recursive ones: http://www.geeksforgeeks.org/iterative-quick-sort/

Despite above optimizations, the function remains recursive and uses function call stack to store intermediate values of l and h. The function call stack stores other bookkeeping information together with parameters. Also, function calls involve overheads like storing activation record of the caller function and then resuming execution.

The above function can be easily converted to iterative version with the help of an auxiliary stack.

Quicksort : Iterative or Recursive

I learnt that recursive algorithms are always slower than their Iterative counterpart.
However the answers point out this is not always true, though I don't see why as arguments were made for the overhead involved with storing the function state on the system stack.

The advantages of using an explicit stack and iteration in place of a recursive implementation are essentially three-fold:

http://www.codeproject.com/Articles/23196/Iterative-Quick-Sort

Using an explicit stack allows the sort to avoid the temporary storage of unnecessary information.
Rather than placing two partitions on a stack in arbitrary order, as a typical recursive Quicksort would implicitly do, the sizes of the

partitions are checked first and the pointers indicating the larger of the two are stacked. The smaller partition's pointers are not stacked at all: we are able to do this since we can guarantee that the smaller partition would always be equivalent to the second recursive call, which is at the tail-end of the function. This leads to the third advantage: Any tail-end recursion can be eliminated and replaced with a simple loop.

Comment on codereview

It will not scale due to recursion: the JVM has no tail call optimization, it will simply grow the method call stack to something proportional to the array to sort, and it will fail for too large an array. (and even for languages/platforms that do have tail call optimization I don't think they'd be able to actually apply it to this code)

Also there were quite a few stack based/iterative implementations of quicksort here but I guess the coders just did it that way for fun?

Answer 1

The link you gave us doesn't say it is faster to use a stack in Java, it says the JVM will stack overflow for a big sorted array. And by the way most (all ?) recursions are implemented with a stack.

Please give the correct link pointing to arguments explaining why stack is faster than recursion. We cannot answer without this.

Answer 2

Recursive algorithms are nearly always stack-based: they use the "call stack", only in the case of tail recursion, the last call record will be overwritten. A potential optimization with using recursion is that increasing the call stack is a single CPU instruction. Thus when it comes to hardware support, sometimes a recursive algorithm will be faster.

In most cases you can optimize the stack (for instance because some parameters like the array to sort are still the same, or because there is only one return address). If this is the case, an explicit stack can be faster.

Some compilers will try to optimize recursive algorithms themselves. But as in nearly all cases of optimization: it's undecidable which algorithm will be faster.