### Logarithmic worst case Stack depth and linearithmic average running time in modified quicksort algorithm linearithmictime sorting quicksort logarithmictime timecomplexity array stack    Posted: 7 years ago Updated: 6 years ago Edit answers (1) views (4145)

How will you modify the algorithm in modified Quicksort algorithm so that the worst case stack depth is $$\theta(logn)$$ maintaining $$O(nlogn)$$ expected running time.

 Posted: 7 years ago 0 0 Edit MODIFIED_Quicksort_NEW(A,p,r) while(p < r) /* Partition and sort the small subarray first */ do q = PARTITION(A,p,r); If(q-p+1 < r-q) MODIFIED_Quicksort_NEW(A,p,q); p = q+1; else MODIFIED_Quicksort_NEW(A,q+1,r); r = q;Since same partitions are done and same subarrays are sorted, expected running time is same - $$O(nlogn)$$.