Quick Sort

Pick a pivot

Quick sort picks one item, the pivot, and splits the rest into “smaller than the pivot” and “bigger than the pivot”. Then it sorts each side the same way.

Think of it like this: A teacher says: “Everyone shorter than Ravi, stand on the left; everyone taller, on the right.” Ravi is now in his final place. Repeat inside each group.

The easy-to-read version

def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[len(nums) // 2]
    smaller = [x for x in nums if x < pivot]
    equal = [x for x in nums if x == pivot]
    bigger = [x for x in nums if x > pivot]
    return quick_sort(smaller) + equal + quick_sort(bigger)

print(quick_sort([10, 7, 8, 9, 1, 5]))

Output

[1, 5, 7, 8, 9, 10]

The in-place version (Lomuto partition)

Real quick sort rearranges the list itself, without making new lists:

def partition(a, low, high):
    pivot = a[high]                 # use the last item as the pivot
    i = low                         # next spot for a "smaller" item
    for j in range(low, high):
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[high] = a[high], a[i]   # put the pivot between the two groups
    return i

def quick_sort(a, low, high):
    if low < high:
        p = partition(a, low, high)
        quick_sort(a, low, p - 1)
        quick_sort(a, p + 1, high)

data = [10, 7, 8, 9, 1, 5]
quick_sort(data, 0, len(data) - 1)
print(data)

Output

[1, 5, 7, 8, 9, 10]

Tip: Picking a random pivot makes quick sort's worst case extremely unlikely. In practice it's often the fastest sort.