Quick Sort is an in-place sorting algorithm that has an O(n logn) time complexity on average. It is a commonly used sorting algorithms today, based on a “divide and conquer” method in which the array is recursively divided into smaller subsets to be sorted.
The Algorithm: The array is first partitioned using a median of three scheme: for an array of size n, we look at the values in indices 0, n-1, and n/2, (light green) and the median value gets swapped into index 0. This value at index 0 is called the pivot (dark green).
We then begin iterating increasingly at index 1, until we find an element whose value is greater than or equal to the pivot (we will call this index i, colored light blue), and iterate decreasingly at index n-1 until we find an element whose value is less than or equal to the pivot (we will call this index j, colored red).
If i < j , both indices become light green to indicate that we are about to make a swap, then we swap the elements at indices i and j, and begin iterating through the array again in the described fashion.
If i > j, then we swap the element at index i-1 with the element at index 0.
Once we have the case that i>j, the pivot is now somewhere in the middle of the array, and every element to the left of the pivot will have values less than or equal to the pivot, and every element to the right of the pivot will have values greater than or equal to the pivot.
Then the algorithm recurses, and the same process is applied to the sub array of indices less than the pivot. We find a new pivot for this sub array, and the algorithm continues to break the array into smaller sub-arrays to sort, and the recursion returns when the size of the sub-array to be sorted has size 1.
Once the right side of the array is sorted, the algorithm is applied to the sub array of indices greater than the original pivot.
Color meaning:
Dark green = pivot element
Light green = three elements compared for median choice
Light blue = left index i
Red = right index j
Dark blue = finished (sorted)
