QuickSort is the most elegant sorting algorithm with an average case time complexity of O(nlogn). The main idea behind quick sort is divide and conquer. I’ll try to explain how this divide and conquer strategy works for quick sort. This writing is a gist from Introduction to Algorithms, 3rd Edition (MIT Press)
Consider an array with randomly distributed integers. We don’t know what the array will look like after sorting. But if we select an element(pivot element) and somehow find out a position for it such that all elements before it is smaller or equal to it and all elements after that are larger than it, we can use that knowledge to divide the array into two sub-arrays, and sort the sub-arrays recursively. This exactly done in the quick sort algorithm. Actually this technique will put the pivot element in its appropriate position if the array were sorted. It will be easier to understand if we follow the below example.
Now let’s select the first element as the pivot element. So in our case 54 is our pivot element. And let’s assume there is some unknown algorithm which can rearrange the array such a way that all elements before the pivot element is smaller or equal to the pivot element and all elements after the pivot element is larger than the pivot element. This clever algorithm is called partitioning and it gives us the following arrangement of the array:
Now look at the arrangement of the above array. All elements before the pivot elements are smaller than the pivot element. And all elements after the pivot element are larger than the pivot element. So this means, if the array were sorted this would be the exact position for our pivot element in the sorted list.
So we get two sub-arrays, one with the elements before the pivot elements and another with the elements after the pivot elements.
Next step will be to sort these sub-arrays based on the same principle. This quicksort algorithm has an average case time complexity of O(nlogn) and worst case time complexity of O(n^2). The worst case complexity occurs when the array is already sorted and we select the pivot element from the same index of the array, say index 0 or index 1 etc. A good practice to overcome this is to select the pivot element randomly providing an average case time complexity of O(nlogn).