Quicksort

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.

Efficiency

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, where n is the length of the original array. In the best case, when the pivot is good, the call stack size is log n.

Implementation

Python:

def quicksort(arr):
  if len(arr) < 2:
    return arr
  else
    pivot = arr[0]
    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)