Quick Sort

The Idea

Choose a pivot and partition the array into a smaller group and a larger group, then sort each group the same way. A good pivot gives O(n log n); a terrible one degrades to O(n²). Random or median-of-three pivots keep that rare.

Real-World Example

Sorting a mountain of laundry by size. You grab one medium shirt, throw everything smaller to the left pile and everything bigger to the right, then repeat inside each pile. The piles shrink startlingly fast.

The Code

def quick_sort(nums):
    if len(nums) <= 1:
        return nums
    pivot = nums[len(nums) // 2]        # middle element as pivot
    smaller = [x for x in nums if x < pivot]
    equal   = [x for x in nums if x == pivot]
    larger  = [x for x in nums if x > pivot]
    # sort the two sides; the equal group is already in place
    return quick_sort(smaller) + equal + quick_sort(larger)

print(quick_sort([8, 3, 8, 1, 5]))      # [1, 3, 5, 8, 8]

nums = [4, 7, 2, 9]
pivot = nums[1]
# everything below the pivot goes left
smaller = [x for x in nums if x ___ pivot]
print(smaller)   # [4, 2]