Quicksort is an efficient and commonly applied array sorting technique, that in a similar way to Binary Search, splits up the search space recursively into halves at each iteration.
At each subdivision, rather than compare each element with each other like in a bubble sort, it compares each element to a “pivot” element and sorts them relative to this pivot. This can be achieved by a “two-pointer” approach. Elements occuring before the pivot index but greater in value to the pivot value are swapped with elements occuring after the pivot index and with values lower than the pivot value. As we subdivide and sort according to a pivot, eventually the array will be sorted.
Each element will be compared to the pivot, for as many subdivisions as are necessary. Hence we have a best case runtime of O(Nlog2(N)). However, the choice of pivot is crucial. It is optimal when the pivot splits the array into two nearly equal groups allowing the most elements to be swapped. Otherwise more elements will not have been compared to the pivot, yet sorting continues, and this leads to O(N^2).
I provide a solution much like Gayle Laakman McDowell’s, where the pivot is chosen to be the midpoint of the subdivision each time (naturally causing an uneven split with an odd number of elements). An alternative by Kernigham and Pike however is to randomly choose a pivot point, which will converge to always being at the centre.