⚠️ This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#912) before relying on it.

Quick Sort

An interactive visualization of the Quick Sort algorithm using the Lomuto partition scheme. Watch how a pivot element partitions the array into smaller and larger halves, then recursively sorts each partition.

Divide and Conquer LeetCode 912 ↗ Medium

The Problem

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in sort functions. The solution should have O(n log n) average time complexity.

Quick Sort achieves this by selecting a pivot element, partitioning the array so all elements less than or equal to the pivot come before it and all greater elements come after, then recursively sorting both partitions.

Interactive Visualization

Array (comma-separated)

Preset

Speed:

Array Visualization

Code

fun quickSort(arr: IntArray, low: Int, high: Int) {    if (low < high) {        val pi = partition(arr, low, high)        quickSort(arr, low, pi - 1)        quickSort(arr, pi + 1, high)    } }fun partition(arr: IntArray, low: Int, high: Int): Int {    val pivot = arr[high]    var i = low - 1    for (j in low until high) {        if (arr[j] <= pivot) {            i++            arr[i] = arr[j].also { arr[j] = arr[i] }        }    }    arr[i+1] = arr[high].also { arr[high] = arr[i+1] }; return i + 1 }

def quickSort(arr, low, high):    if low < high:        pi = partition(arr, low, high)        quickSort(arr, low, pi - 1)        quickSort(arr, pi + 1, high)def partition(arr, low, high):    pivot = arr[high]    i = low - 1    for j in range(low, high):        if arr[j] <= pivot:            i += 1            arr[i], arr[j] = arr[j], arr[i]    arr[i + 1], arr[high] = arr[high], arr[i + 1]    return i + 1

Status

Press Step or Play to begin.

How It Works

Key Insight

Quick Sort works by choosing a pivot element and partitioning the array around it. After partitioning, the pivot is in its final sorted position — all elements to its left are smaller or equal, and all elements to its right are larger. This divide-and-conquer approach recursively sorts both halves, resulting in a fully sorted array without needing to merge.

The Algorithm (Lomuto Partition Scheme)

Choose pivot: Select the last element as the pivot (pivot = arr[high])
Initialize boundary: Set i = low - 1 as the boundary between elements ≤ pivot and elements > pivot
Scan with j: Iterate j from low to high - 1
If arr[j] ≤ pivot: Increment i and swap arr[i] with arr[j], expanding the "less than or equal" region
Place pivot: After the loop, swap arr[i + 1] with arr[high] to place the pivot in its correct position
Recurse: Recursively sort the left partition (low to pi - 1) and the right partition (pi + 1 to high)

Complexity

Time (Average) O(n log n)

Time (Worst) O(n²)

Space O(log n)

On average, each partition divides the array roughly in half, giving O(log n) levels of recursion with O(n) work per level. The worst case occurs when the pivot is always the smallest or largest element (e.g., already sorted input with last-element pivot), leading to O(n²) time. The space complexity of O(log n) comes from the recursion stack depth.