With a little effort, we can limit the maximum depth of recursion to approximately Olg(n), even in the worst case.
- Then the extra space required will be O(lg(n)) — insignificant compared to the O(n) space for the array being sorted.
- Note, however, the worst case running time remains O($n^{2}$)
voidquicksort2( T[] A, Integer left, Integer right)
{
while ( left < right )
{
q = partition(A,left,right);
if ( q-left < right-q )
{
quicksort2(A,left,q–1); // Recursive call sorts smaller sublist
left = q + 1; // Loop back to sort larger sublist
}
else
{
quicksort2(A,q+1,right); // Recursive call sorts smaller sublist
right =q-1; // Loop back to sort larger sublist
}
}
Here with better programming using Tail call, we can limit the O(n) stack frame in worst case. Each time quicksort2() calls itself recursively, it does so only for the smaller of the two sublists. This means that each time the depth of recursion rises by one, the size of the input to quicksort2() is cut at least in half. Thus the depth of recursion cannot exceed lg(n).
That is the reason behind everywhere quicksort space complexity is written as O(log n). Because we can optimize the standard quicksort using tail recursion to limit the stack frame as maximum log n, still the time complexity in worst case remains same.
