Quicksort is a fast and efficient sorting algorithm which recursively divides sub-arrays and sorts them around a “pivot”.
If the array has zero or one items, it doesn’t need to be sorted. This is the base case. Otherwise, a pivot is selected and all array items are partitioned according to whether they’re less-than-or-equal-to or greater-than the pivot value. Then, these partitions are recursed upon. The results of each recursive step are concatenated.
As long as a good pivot is used, quicksort averages
O(n log n) (logarithmic linear time/space) in Big O notation. This logarithmic aspect happens because, with each recursive step, the number of items in the array being operated on is reduced (ideally by a factor of 2, AKA in half). Quicksort uses a divide-and-conquer (D and C) approach to sorting.
Ultimately, quicksort speed depends on pivot selection, since the speed of quicksort relies on dividing the arrays into smaller sub-arrays to reduce the number of steps necessary to complete the operation. If the pivot is always the minimum value in the sub-array, the new sub-array will only contain one less item than the previous sub-array. This results in a call stack size of
n is the length of the original array. In the best case, when the pivot is good, the call stack size is
def quicksort(arr): if len(arr) < 2: return arr else pivot = arr less = [i for i in arr[1:] if i <= pivot] more = [i for i in arr[1:] if i > pivot] return quicksort(less) + pivot + quicksort(more)