Quick Sort

Intuition

After a partition step the pivot lands in its correct final position, with all smaller elements to its left and all larger ones to its right. Neither side needs to know about the other, so the algorithm recurses independently on each. The catch is that a poorly chosen pivot (for example, always taking the last element of an already-sorted array) degrades to quadratic time. Selecting the pivot uniformly at random makes those bad splits vanishingly unlikely, so the expected work stays O(n log n) while the sort remains fully in place.

Algorithm walkthrough

1. 1Call quicksort on the full index range [0, length - 1].
2. 2If the range has fewer than two elements it is already sorted, so stop.
3. 3Swap a randomly chosen element to the end to act as the pivot, then scan the range moving every value smaller than the pivot to the front.
4. 4Swap the pivot into the boundary position; it is now in its final sorted location.
5. 5Recurse on the sub-range left of the pivot and the sub-range right of the pivot.

Implementation

import random
from typing import List


class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        self._quicksort(nums, 0, len(nums) - 1)
        return nums

    def _quicksort(self, nums: List[int], lo: int, hi: int) -> None:
        if lo >= hi:
            return
        p = self._partition(nums, lo, hi)
        self._quicksort(nums, lo, p - 1)
        self._quicksort(nums, p + 1, hi)

    def _partition(self, nums: List[int], lo: int, hi: int) -> int:
        r = random.randint(lo, hi)
        nums[r], nums[hi] = nums[hi], nums[r]
        pivot = nums[hi]
        i = lo
        for j in range(lo, hi):
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[hi] = nums[hi], nums[i]
        return i