Quick sort

Problem¶

Implement in-place three-way randomized quicksort for a Python list.

Key trick¶

Partition the range into values smaller than, equal to, and greater than the pivot.

Trap¶

A poor pivot can cause \(O(n^2)\) time and \(O(n)\) recursion depth; two-way partitioning also handles many duplicates poorly.

Why is it interesting?¶

It tests partition invariants and is fast for arrays, but merge sort is normally preferable for linked lists.

Python solution¶

class sort_quick_sort:
    def sort(self, nums: list[int]) -> list[int]:
        # Preserve the caller's input.
        arr = nums[:]

        self._sort_range(arr, 0, len(arr) - 1)
        return arr

    def _sort_range(
        self,
        arr: list[int],
        lo: int,
        hi: int,
    ) -> None:
        # Ranges are inclusive: `[lo, hi]`.
        if lo >= hi:
            return

        # Randomization makes consistently bad pivots unlikely.
        pivot = arr[random.randrange(lo, hi + 1)]

        # Three-way partition invariant:
        #
        # `[lo, l)` contains values smaller than the pivot.
        # `[l, i)` contains values equal to the pivot.
        # `[i, r]` is unclassified.
        # `(r, hi]` contains values greater than the pivot.
        l = lo
        i = lo
        r = hi

        while i <= r:
            if arr[i] < pivot:
                # Grow the smaller region and classify `i`.
                arr[l], arr[i] = arr[i], arr[l]
                l += 1
                i += 1
            elif arr[i] > pivot:
                # Move this value into the greater region.
                # Do not advance `i`: the swapped-in value has
                # not yet been classified.
                arr[i], arr[r] = arr[r], arr[i]
                r -= 1
            else:
                # Grow the equal region.
                i += 1

        # The equal region is already in its final location.
        self._sort_range(arr, lo, l - 1)
        self._sort_range(arr, r + 1, hi)