Question

What is the runtime for quick sort?

Answer 1

The running time of Quicksort will depend on how balanced the partitions are. If you are unlucky and select the greatest or the smallest element as the pivot, then each partition will separate only one element at a time, so the running time will be similar to Insertion Sort.

However, Quicksort will usually pick a pivot that is mid-range, and it will partition the array into two parts. Let's assume Partition is lucky and it always picks the median element as the pivot.

Running Time of Recursive Methods
Quicksort is a recursive method, so we will have to use a technique to calculate the total running time of all the method calls. We can use a version of the "Recursion Tree Method" to estimate the running time for a given array of N elements.

Each time partition is called on a sub-array, each element in the sub-array needs to be compared to the pivot element. Since all the sub-arrays are passed to partition, there will be N total operations for each level of the tree.

How many levels will it take for the Quicksort to finish? Since we assume it always picks the middle element, the array will be split into two equal halves each time. So it will take log(N) splits until we get single elements in the sub-arrays. Since there is log(N) levels and each one involves N operations, the total running time for Quicksort will be N*log(N).