Quick Sort Visualizer

How it works

1. If the range A[lo..hi] has fewer than two elements, return.
2. Choose a pivot: last, first, middle, random element or median of three — the visualizer offers all five.
3. Partition. Lomuto: park the pivot at A[hi], scan j from lo to hi − 1 and swap every element ≤ pivot into a growing left region, then swap the pivot in right after that region — it is now in its final position p. Hoare: two pointers move inward from both ends and swap each pair that is on the wrong side.
4. Recursively sort both parts: lo..p − 1 and p + 1..hi for Lomuto, lo..p and p + 1..hi for Hoare.
5. There is no combine step: once both sides are sorted, the whole range is sorted.

Worked example: sorting [38, 27, 43, 3, 9, 82, 10]

With the visualizer's default settings — Lomuto partition, last-element pivot:

• Partition A[0..6] around 10. Only 3 and 9 are ≤ 10, so they are swapped to the front and 10 lands at index 2: [3, 9, 10, 38, 27, 82, 43]. 10 is now in its final place.
• Left side A[0..1], pivot 9: 3 ≤ 9 and nothing moves; 9 is final.
• Right side A[3..6], pivot 43: 38 and 27 are ≤ 43 and already in front, 82 isn't, so 43 swaps with 82: [3, 9, 10, 38, 27, 43, 82].
• A[3..4], pivot 27: 38 > 27, so 27 swaps to the front of the range: [3, 9, 10, 27, 38, 43, 82].

That is 11 comparisons and 5 swaps — fewer comparisons than merge sort's 14 on the same input. Switch to Hoare partitioning or another pivot rule in the Options panel and watch the recursion tree change shape.

Why the pivot decides everything

If every pivot splits its range roughly in half, the recursion is about log₂ n levels deep and each level partitions n elements: O(n log n). Even a consistent 90/10 split is still O(n log n), with a bigger constant.

The disaster is a pivot that is always the smallest or largest element. Each partition then peels off a single element, the recursion is n levels deep and the comparisons add up to n(n − 1)/2: O(n²). With a last-element pivot that is exactly what an already sorted or reversed array does. In the visualizer a sorted array of 16 values costs 120 comparisons with the last-element pivot and 38 with the middle one — load the Sorted preset and watch the recursion tree turn into a long chain.

Choosing a pivot

• Last or first element: simplest, but O(n²) on sorted or reversed input, which is common in real data.
• Middle element: fine on sorted and reversed input; crafted inputs can still defeat it.
• Random element: expected O(n log n) on every input; the worst case still exists but is astronomically unlikely.
• Median of three (first, middle and last): cheap, avoids the sorted-input trap and gives more balanced splits. Production quick sorts use it or a larger sample.

Libraries add one more safety net: introsort (C++ std::sort) tracks the recursion depth and switches to heap sort once it exceeds about 2·log₂ n, which guarantees O(n log n).

Lomuto vs Hoare partitioning

Lomuto (the default here, as in CLRS) keeps one boundary i: everything left of it is ≤ pivot. It is easy to get right and leaves the pivot in its final position, so the recursive calls can skip it. Its weakness is duplicates: if all keys are equal, every element is ≤ pivot, each split is n − 1 against 0, and the sort goes quadratic — 120 comparisons for 16 equal values in the visualizer.

Hoare (Tony Hoare's original scheme) moves two pointers towards each other and swaps a pair only when both elements are on the wrong side. It usually swaps less, and because both pointers stop on keys equal to the pivot, an array of equal values splits down the middle. The pivot does not necessarily end in its final position, so the recursion uses lo..p and p + 1..hi.

For inputs with many duplicates, three-way partitioning (< pivot, = pivot, > pivot — Dijkstra's Dutch national flag problem) is better still: all keys equal to the pivot are finished after one pass.

Stability, memory and quickselect

Quick sort is not stable: partition swaps move elements across long distances, so equal keys can change order. It is in-place apart from the recursion stack, which is O(log n) deep on average but O(n) in the worst case; recursing into the smaller side first and looping over the larger side caps it at O(log n).

A favourite interview follow-up is “find the k-th smallest element”: quickselect partitions once and recurses into one side only, O(n) on average.

Time and space complexity

Quick Sort in Python

import random


def quick_sort(A, lo=0, hi=None, scheme="lomuto", rule="last"):
    # Sorts A[lo..hi] (inclusive) in place. NOT stable.
    # O(n log n) on average, O(n^2) worst case (bad pivots).
    # scheme: "lomuto" | "hoare"
    # rule:   "last" | "first" | "middle" | "random" | "median3"
    if hi is None:
        hi = len(A) - 1
    if lo >= hi:                        # 0 or 1 element
        return
    if scheme == "lomuto":
        p = partition_lomuto(A, lo, hi, rule)   # pivot lands at p
        quick_sort(A, lo, p - 1, scheme, rule)
        quick_sort(A, p + 1, hi, scheme, rule)
    else:
        p = partition_hoare(A, lo, hi, rule)    # A[lo..p] <= A[p+1..hi]
        quick_sort(A, lo, p, scheme, rule)
        quick_sort(A, p + 1, hi, scheme, rule)


def choose_pivot(A, lo, hi, rule):
    # Index of the pivot for A[lo..hi].
    mid = (lo + hi) // 2
    if rule == "first":
        return lo
    if rule == "middle":
        return mid
    if rule == "random":
        return random.randint(lo, hi)   # lo..hi inclusive
    if rule == "median3":               # median of A[lo], A[mid], A[hi]
        return sorted((lo, mid, hi), key=lambda k: A[k])[1]
    return hi                           # "last"


def partition_lomuto(A, lo, hi, rule="last"):
    k = choose_pivot(A, lo, hi, rule)
    A[k], A[hi] = A[hi], A[k]           # park the pivot at A[hi]
    pivot = A[hi]
    i = lo - 1                          # end of the <= region
    for j in range(lo, hi):             # j = lo .. hi-1
        if A[j] <= pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[hi] = A[hi], A[i + 1]   # pivot to its final spot
    return i + 1


def partition_hoare(A, lo, hi, rule="last"):
    k = choose_pivot(A, lo, hi, rule)
    A[k], A[lo] = A[lo], A[k]           # park the pivot at A[lo]
    pivot = A[lo]
    i, j = lo - 1, hi + 1
    while True:
        i += 1                          # do i = i + 1 while A[i] < pivot
        while A[i] < pivot:
            i += 1
        j -= 1                          # do j = j - 1 while A[j] > pivot
        while A[j] > pivot:
            j -= 1
        if i >= j:                      # pointers crossed
            return j
        A[i], A[j] = A[j], A[i]

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Merge Sort VisualizerMerge sort splits the array in half, sorts each half recursively and merges the sorted halves, in O(n log n) time. Watch every split and merge animated.
• Heap Sort VisualizerHeap sort visualizer: build a max-heap, then swap the root to the end and sift down, step by step. O(n log n) worst case, in place but not stable, with code.
• Insertion Sort VisualizerInsertion sort takes each element and slides it left into place in the sorted prefix. Watch every shift animated, with Python code and O(n²) complexity.
• Selection Sort VisualizerSelection sort finds the smallest unsorted element and swaps it to the front, one position per pass. See every comparison animated, with code and complexity.
• Sorting Algorithm VisualizerSorting algorithm visualizer: watch bubble, selection, insertion, shell, counting, radix, merge and quick sort step by step, then race them in Compare mode.