QuickSort - Code

Here is the implementation of quicksort:

function quickSort(arr, low, high):
    if low < high:
        pivotIdx = partition(arr, low, high)
        quickSort(arr, low, pivotIdx - 1)
        quickSort(arr, pivotIdx + 1, high)

Time: $O(n \log n)$ average. $O(n^2)$ worst case (already sorted with bad pivot choice).

Space: $O(\log n)$ average for recursion stack. $O(n)$ worst case.

Stability: Unstable. Partitioning swaps elements across the pivot.

Optimization: Use randomized pivot or median-of-three to avoid $O(n^2)$ on sorted input. Most library implementations use introsort: quicksort that switches to heapsort if recursion gets too deep.