Quick Sort

Given an unsorted array, rearrange it in ascending order. Quick sort picks one element (the pivot), places it at its correct position where everything left is smaller and everything right is larger, then recurses on both sides. Once every element has served as a pivot once, the array is sorted.

One Deep Walkthrough: [7, 2, 9, 1, 6, 3, 8]

Pivot strategy: pick the last element.

Initial array: [7, 2, 9, 1, 6, 3, 8], pivot = 8.

We maintain a pointer small_end that tracks the boundary between the "small bucket" (elements ≤ pivot) and the "large bucket". Start with small_end = -1 (the small bucket is empty). Scan left to right with index i.

Step 1 — i=0, arr[0]=7. Is 7 ≤ 8? Yes. Advance small_end to 0. Swap arr[0] with arr[0] (self-swap).

Step 2 — i=1, arr[1]=2. Is 2 ≤ 8? Yes. small_end becomes 1. Self-swap.

Step 3 — i=2, arr[2]=9. Is 9 ≤ 8? No. small_end stays at 1. No action.

Step 4 — i=3, arr[3]=1. Is 1 ≤ 8? Yes. small_end → 2. Swap arr[2] with arr[3]: the 1 goes into the small bucket, the 9 moves right.

Step 5 — i=4, arr[4]=6. Is 6 ≤ 8? Yes. small_end → 3. Swap arr[3] with arr[4].

Step 6 — i=5, arr[5]=3. Is 3 ≤ 8? Yes. small_end → 4. Swap arr[4] with arr[5].

Step 7 — place the pivot. After the scan, indices 0–4 contain elements ≤ pivot. Index 5 is the first element > pivot. Swap arr[5] (9) with the pivot position arr[6] (8).

Pivot 8 is at index 5 — its final sorted position. Left subarray: [7, 2, 1, 6, 3]. Right subarray: [9] (trivially sorted).

Recurse on left [7, 2, 1, 6, 3], pivot = 3:

Place pivot: swap arr[2] (7) with arr[4] (3) → [2, 1, 3, 6, 7]. Pivot 3 at index 2.

Recurse left [2, 1], pivot = 1: swap arr[0] (2) with arr[1] (1) → [1, 2].

Recurse right [6, 7], pivot = 7: self-swap → [6, 7].

Final: [1, 2, 3, 6, 7, 8, 9].

Code

def quick_sort(arr, left, right):
    if left >= right:
        return

    pivot_index = partition(arr, left, right)
    quick_sort(arr, left, pivot_index - 1)
    quick_sort(arr, pivot_index + 1, right)


def partition(arr, left, right):
    pivot = arr[right]
    small_end = left - 1

    for i in range(left, right):
        if arr[i] <= pivot:
            small_end += 1
            arr[small_end], arr[i] = arr[i], arr[small_end]

    arr[small_end + 1], arr[right] = arr[right], arr[small_end + 1]
    return small_end + 1

Line by line (quick_sort):

• if left >= right: return — base case. A single element (left == right) or empty slice (left > right) needs no sorting.
• pivot_index = partition(arr, left, right) — partition the slice. Returns the pivot's final position.
• quick_sort(arr, left, pivot_index - 1) — sort everything left of the pivot.
• quick_sort(arr, pivot_index + 1, right) — sort everything right of the pivot.

Inside partition:

• pivot = arr[right] — pick the last element as pivot. Simple, but can degrade on already-sorted input.
• small_end = left - 1 — the small bucket is initially empty. Since left may not be 0 in recursive calls, starting at left - 1 avoids assuming the array starts at 0.
• for i in range(left, right): — scan from left to right - 1. The pivot at right is excluded.
• if arr[i] <= pivot: — this element belongs in the small bucket.
• small_end += 1; swap(arr[small_end], arr[i]) — expand the small bucket and bring the element into it.
• After the loop: swap(arr[small_end + 1], arr[right]) — place the pivot between the small and large buckets. small_end + 1 is the first position after all small elements.
• return small_end + 1 — return the pivot index.

Edge case — two elements [5, 2] (left=0, right=1). Pivot = 2. small_end = -1. i=0: arr[0]=5 ≤ 2? No. Loop ends. Swap arr[0] (5) with arr[1] (2) → [2, 5]. Pivot at index 0. Correct.

Edge case — all identical. Every element ≤ pivot. Every element gets swapped into the small bucket. The pivot ends at the last position. Left recursion gets n-1 elements, all identical. Continues until size 1.

Time: Average O(n log n). Worst O(n²) (already-sorted with last-element pivot). Space: O(log n) recursion stack.

Code Trace

Tracing quick_sort([7, 2, 9, 1, 6, 3, 8], 0, 6):

With a random pivot (swap a random element to arr[right] before partitioning), the O(n²) worst case becomes vanishingly unlikely in practice.

→ LeetCode 912: Sort an Array — quick sort with random pivot. LeetCode 215: Kth Largest Element — quick select uses the same partition logic.