CODEWITHSUNDEEP
algorithmrecursioniterationquicksort
Shubhang Gupta
Shubhang Gupta

Reputation: 138

Quick sort with variation in recursive calls

I was trying the implementation of quicksort with a small variation as follows: The usual implementation of quicksort makes two recursive calls. In order to optimize stack space, it recurses on the smaller subarray as usual and whenever it needs to recurse on the larger subarray, it uses an iterative module instead. So, for this kind of variation in quick sort what will be the depth of recursion in comparison to the usual implementation of the quick sort?

Upvotes: 1

Views: 407

Answers (1)

rcgldr
rcgldr

Reputation: 28911

In that case, stack space complexity is O(log2(n)) (I included the 2, even though it is a constant).

Note this method is very similar to the original implementation of quicksort, which was first implemented on a machine without a native stack. The order of operations is still the same, process smaller sub-partitions before larger sub-partitions, but when using a programmed stack, the indexes (or pointers) for the larger sub-partition are pushed onto the stack to be sorted later, and the code loops back to sort the smaller sub-partition.

Upvotes: 1

Related Questions