csortingquicksortspace-complexity

Can quicksort be implemented in C without stack and recursion?


I found this post How to do iterative quicksort without using stack in c? but the answer suggested does use a inline stack array! (Only constant amount of extra space is permitted)


Solution

  • Apparently, it is possible to implement a non-recursive quicksort with only constant amount of extra space as stated here. This builds upon the Sedgewick's work for non-recursive formulation of quicksort. Instead of preserving the boundary values(low and high) it essentially performs a linear scan to determine these bounds.