# QuickSort

Quicksort uses a divide and conquer approach to sorting an array, and leverages recursion.

Essentially, you pick a pivot number from the array to be sorted, it can be any number:

`[4, 6, 2, 1, 5]`

Let’s pick 2.

Now partition the array into two sub-arrays, the numbers less than or equal to the pivot are added to the first sub-array (less), those greater are added to the second sub-array (greater):

```pivot   = 2
less    = 
greater = [4, 6, 5]```

Note: Remember to skip the number you chose as a pivot when building your sub-arrays.

The last step is to recursively call quicksort on the two sub-arrays, joining the results to the pivot:

quicksort(less) +  + quicksort(greater)

Here’s the implementation, notice how we picked the first number in the array as our pivot, this makes it easy to skip.

``````def quicksort(array):
if len(array) < 2:
return array

# pick the first number in the array
pivot = array

less = []
greater = []

# skip our pivot number, start from the second
for i in array[1:]:
if i <= pivot:
less.append(i)
else:
greater.append(i)

return quicksort(less) + [pivot] + quicksort(greater)

print(quicksort([7, 11, 5, 2, 44, 21, 3, 18, 1]))

# outputs:

[1, 2, 3, 5, 7, 11, 18, 21, 44]``````

The same, more concisely:

``````def quicksort(array):
if len(array) < 2:
return array

pivot = array

less = [x for x in array[1:] if x <= pivot]
greater = [x for x in array[1:] if x > pivot]

return quicksort(less) + [pivot] + quicksort(greater)``````