## QuickSort Algorithm Working Principle

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) , a cool book for algorithm enthusiasts.

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.