# 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)
``````