Quicksort
Now, let's study the famous quicksort algorithm!
Introduction
Quicksort is the fastest known comparisonbased sorting algorithm for arrays in the average case.
Caveat: Merge sort works better on linked lists, and there are other noncomparison based algorithms that outperform quicksort.
$$$$
Quick sort algorithm

Start with an array of n elements.

Choose a pivot element from the array to be sorted.

Partition the array into two unsorted subarrays, such that all elements in one subarray are less than the pivot and all the elements in the other subarray are greater than the pivot.

Elements that are equal to the pivot can go in either subarray.

Sort each subarray recursively to yield two sorted subarrays.

Concatenate the two sorted subarrays and the pivot to yield one sorted array.
Note that if we always pick the smallest element in the array as the pivot, the lefthand side array is always empty, and all the remaining items end up in the righthand side array. This means that the array will be subdivided a total of $O(n)$ times. Since the partitioning takes $O(n)$ time for each divide step., this has a total time complexity of $O(n^2)$. This is the worstcase time complexity for Quicksort because the depth of recursion is maximum.
The following set of slides shows the partitioning at each recursive depth for a worstcase scenario
Level up your interview prep. Join Educative to access 70+ handson prep courses.