Quicksort Big O

On average, quicksort has a Big O of O(n*log(n)). In the worst case, and assuming we don't take any steps to protect ourselves, it can degrade to O(n^2). partition() has a single for-loop that ranges from the lowest index to the highest index in the array. By itself, the partition() function is O(n). The overall complexity of quicksort is dependent on how many times partition() is called.

Worst case: The input is already sorted. An already sorted array results in the pivot being the largest or smallest element in the partition each time, so each call only peels off one element. That's n levels of recursion, each doing up to n work in partition().

Best case: The pivot is the middle element of each sublist, which results in only log(n) levels of recursion, each doing n total work in partition().

def quick_sort(nums: list[int], low: int, high: int) -> None:
    if low < high:
        p = partition(nums, low, high)
        quick_sort(nums, low, p - 1)
        quick_sort(nums, p + 1, high)


def partition(nums: list[int], low: int, high: int) -> int:
    pivot = nums[high]
    i = low
    for j in range(low, high):
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[high] = nums[high], nums[i]
    return i