Quick Sort

A divide-and-conquer algorithm that picks a pivot, partitions elements around it, then recursively sorts each partition.

Complexity

Time (Best)

O(n log n)

Time (Avg)

O(n log n)

Time (Worst)

O(n²)

Space

O(log n)

Key Points

›Average O(n log n) with very low constant factor — fastest in practice for most inputs
›Worst case O(n²) occurs with sorted/reverse-sorted input and a bad pivot choice
›Randomized pivot or median-of-three strategy prevents worst case
›In-place: O(log n) stack space from recursion only
›Not stable by default; used in most standard library sort implementations

Interactive Visualizer

Step 0 / 0✓ Sorted!

SlowFast

DefaultComparingSwappingSorted

Code Examples

Swift

func quickSort(_ arr: inout [Int], _ low: Int, _ high: Int) {
    guard low < high else { return }
    let pi = partition(&arr, low, high)
    quickSort(&arr, low, pi - 1)
    quickSort(&arr, pi + 1, high)
}

func partition(_ arr: inout [Int], _ low: Int, _ high: Int) -> Int {
    let pivot = arr[high]
    var i = low - 1
    for j in low..<high {
        if arr[j] <= pivot { i += 1; arr.swapAt(i, j) }
    }
    arr.swapAt(i + 1, high)
    return i + 1
}

var nums = [10, 7, 8, 9, 1, 5]
quickSort(&nums, 0, nums.count - 1)
print(nums)  // [1, 5, 7, 8, 9, 10]

Practice Problems

Kth Largest Element in an Array

MediumLeetCode ↗

Sort an Array

MediumLeetCode ↗

Wiggle Sort II

MediumLeetCode ↗