Python quicksort and partitioning
Quicksort partitions values into those below, equal to, and above a pivot. Only the below and above groups need recursive sorting.
Python
def quick_sort(values):
if len(values) <= 1:
return values.copy()
pivot = values[len(values) // 2]
lower = [value for value in values if value < pivot]
equal = [value for value in values if value == pivot]
upper = [value for value in values if value > pivot]
return quick_sort(lower) + equal + quick_sort(upper)
print(quick_sort([3, 1, 2, 1]))
assert quick_sort([]) == []
assert quick_sort([2, 2]) == [2, 2]