Iterative Implementation of Quicksort

Write iterative version of recursive Quicksort algorithm.


In the previous post, we have discussed the recursive implementation of Quicksort algorithm. We have seen that we can optimize Quicksort recursion stack by using tail recursion to minimize the recursive depth. Tail recursion makes sure that at most O(log n) space is used by recursing first into the smaller side of the partition, then using a tail call to recurse into the other. Tail recursion should be recognized by the compiler and optimized to its iterative counterpart.

We have also talked about another recursive stack space optimization. The idea was that when the number of elements in sub-array is below some threshold k (perhaps ten elements), we switch to a non-recursive sorting algorithm such as insertion sort or simply stop processing the subarray and later perform insertion sort on it (in O(kn) time) as each element will be at most k positions away from its final sorted position.

But despite these performance boosts, the algorithm remains recursive in nature. Can we convert the algorithm into an iterative one? In this post, its iterative implementation is discussed.

The idea is to use a stack for storing sub-array starting & ending index and for later processing instead of using recursion. Note that the partitioning logic would remain the same.

Below is iterative C++ and Java implementation of Quicksort algorithm:


Download   Run Code


-6 -3 1 2 3 5 6 8 9


Download   Run Code


[-6, -3, 1, 2, 3, 5, 6, 8, 9]

Exercise: Modify above code to print in descending order.

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of