Quick Sort

Introduction

Running Time

Choosing the pivot randomly is known to be the best way of performing quick sort because on an average it achieves a run time of nlogn. 

QuestionDefine the recursion depth of QuickSort to be the maximum no. of successive recursive calls before it hits the base case [Note: the recursion depth is a random variable, which depends on which pivots get chosen.]. What is the minimum-possible and maximum-possible recursion depth of Quicksort respectively?
Ans
Best Case: When the algorithm always picks the median as a pivot, in which case the recursion is essentially identical to that in MergeSort - Θ(log(n)). 
Worst Case: The min or the max is always chosen as the pivot, resulting in linear depth - Θ(n)

Source Code

1. Taking the first element as the pivot: code
2. Taking the last element as the pivot: code
3. Taking the median (amongst the first, last and middle element) as the pivot: code