Quicksort Time Complexity

• Best case: O(n log n) — when the pivot divides the array roughly in half each time.
• Average case: O(n log n) — expected performance with random input.
• Worst case: O(n²) — occurs when the pivot is always the smallest or largest element.

The worst case can be mitigated using randomized pivot selection or the median-of-three strategy.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + mid + quicksort(right)