How to optimize quicksort so that the On2 worst case run tim

How to optimize quicksort so that the O(n^2) worst case run time behaviour does not occur?

Solution

The worst case occurs when the picked pivot is always an extreme (smallest or largest) element. This happens when input array is sorted or reverse sorted and either first or last element is picked as pivot.

We can use randomized QuickSort to achieve O(nLogn) worst case. The idea is based on the fact that the median element of an unsorted array can be found in linear time. So we find the median first, then partition the array around the median element.

void quickSort(int arr[], int l, int h)
{
if (l < h)
{
// Find size of current subarray
int n = h-l+1;

// Find median of arr[].
int med = kthSmallest(arr, l, h, n/2); // we can find kth smallest element in unsorted array in linear time

// Partition the array around median
int p = partition(arr, l, h, med);

// Recur for left and right of partition
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, h);
}
}