Sorting Tested code in 3 languages

Quick Sort, Visualized Step by Step

Pick a pivot, move smaller values to its left and bigger values to its right, then do the same to each side. Press play to watch every comparison and swap, next to the exact line of code that runs.

Crio.Do · Last updated 18 November 2026

Interactive quick sort

Sort indices 0–7 (8 values).

0Comparisons
0Swaps
1/–Step
def quick_sort(a, lo=0, hi=None):    if hi is None:        hi = len(a) - 1    if lo < hi:        p = partition(a, lo, hi)        quick_sort(a, lo, p)        quick_sort(a, p + 1, hi)  def partition(a, lo, hi):    pivot = a[(lo + hi) // 2]    i, j = lo - 1, hi + 1    while True:        i += 1        while a[i] < pivot:            i += 1        j -= 1        while a[j] > pivot:            j -= 1        if i >= j:            return j        a[i], a[j] = a[j], a[i]

The highlighted line is the one the animation is running. This is the exact code we test.

Tip: use the arrow keys to step when the visualizer has focus. Try duplicates, a sorted list or your own numbers.

On this page
  1. How it works
  2. Worked example
  3. Complexity
  4. When to use it
  5. Common mistakes
  6. Interview questions
  7. FAQ
  8. Sources

How quick sort works

Quick sort is a divide-and-conquer sort. It picks one value, the pivot, and rearranges the range so that everything on the left is ≤ the pivot and everything on the right is ≥ it. That rearranging is called partitioning. Then it sorts the left part and the right part the same way, until every part holds a single value.

Think of a teacher sorting exam papers by marks. She picks one paper, say 60 marks, and makes two piles: lower marks on the left, higher on the right. She never compares a paper in the left pile with one in the right pile again. Each pile gets the same treatment until every pile is a single paper.

This page uses Hoare's partition scheme with the middle element as the pivot. Two pointers start outside the ends of the range. i walks right until it finds a value that is not smaller than the pivot; j walks left until it finds a value that is not bigger. If they have not crossed, those two values sit on the wrong sides, so they swap. When the pointers meet or cross, the range splits after j.

Why Hoare and not Lomuto, the textbook version that uses the last element as the pivot? Hoare's scheme does fewer swaps, and because both pointers stop on values equal to the pivot, an array full of duplicates still splits near the middle. Lomuto puts all the equal values on one side, and on an all-equal array it slows down to O(n²).

The algorithm in 5 steps

  1. 1 If the range holds one value, stop: it is already sorted.
  2. 2 Take the middle value of the range as the pivot.
  3. 3 Move i right past values smaller than the pivot, and j left past values bigger than the pivot.
  4. 4 If i is still left of j, swap a[i] and a[j] and keep scanning.
  5. 5 When i meets or passes j, sort lo..j and j+1..hi the same way.

Worked example

Here is the full run on a fixed array, generated by the same code as the visualizer. To keep it short, the table shows pivot choices, swaps and finished splits; the comparisons in between are counted in the total but not listed.

Input: [8, 3, 5, 1, 9, 2, 7]

  1. Step 2 Pivot = 1, the middle value of indices 0–6 (index 3). 8351927
  2. Step 8 Swap 8 and 1: each was on the wrong side of pivot 1. 1358927
  3. Step 13 i (1) has passed j (0), so this split is done: index 0 holds values ≤ 1, indices 1–6 hold values ≥ 1. 1358927
  4. Step 17 Pivot = 8, the middle value of indices 1–6 (index 3). 1358927
  5. Step 22 Swap 8 and 7: each was on the wrong side of pivot 8. 1357928
  6. Step 25 Swap 9 and 2: each was on the wrong side of pivot 8. 1357298
  7. Step 28 i (5) has passed j (4), so this split is done: indices 1–4 hold values ≤ 8, indices 5–6 hold values ≥ 8. 1357298
  8. Step 30 Pivot = 5, the middle value of indices 1–4 (index 2). 1357298
Show the remaining 11 rows
  1. Step 34 Swap 5 and 2: each was on the wrong side of pivot 5. 1327598
  2. Step 38 i (3) has passed j (2), so this split is done: indices 1–2 hold values ≤ 5, indices 3–4 hold values ≥ 5. 1327598
  3. Step 40 Pivot = 3, the middle value of indices 1–2 (index 1). 1327598
  4. Step 43 Swap 3 and 2: each was on the wrong side of pivot 3. 1237598
  5. Step 46 i (2) has passed j (1), so this split is done: index 1 holds values ≤ 3, index 2 holds values ≥ 3. 1237598
  6. Step 52 Pivot = 7, the middle value of indices 3–4 (index 3). 1237598
  7. Step 55 Swap 7 and 5: each was on the wrong side of pivot 7. 1235798
  8. Step 58 i (4) has passed j (3), so this split is done: index 3 holds values ≤ 7, index 4 holds values ≥ 7. 1235798
  9. Step 64 Pivot = 9, the middle value of indices 5–6 (index 5). 1235798
  10. Step 67 Swap 9 and 8: each was on the wrong side of pivot 9. 1235789
  11. Step 70 i (6) has passed j (5), so this split is done: index 5 holds values ≤ 9, index 6 holds values ≥ 9. 1235789

Total for this run: 35 comparisons and 7 swaps, in 75 animation steps. Result: 1, 2, 3, 5, 7, 8, 9.

Time and space complexity

Best

O(n log n)

Every pivot lands near the middle, so each level halves the ranges: about log₂ n levels with about n comparisons each.

Average

O(n log n)

Some splits are lopsided, but on typical inputs they are balanced often enough to keep the recursion depth proportional to log n.

Worst

O(n²)

If every pivot is the smallest or largest value, each partition removes only one element: n + (n−1) + … + 1 comparisons.

Space

O(log n)

No extra array, but recursion uses stack frames: O(log n) deep on average, O(n) in the worst case.

Stable:
No
In place:
Yes
Partition:
Hoare
Pivot:
Middle element

On the 8 numbers in the visualizer above, quick sort makes 38 comparisons and 5 swaps; merge sort makes 16 comparisons and 24 writes on the same array. Counts like these depend on the input and the exact variant, which is why complexity is stated as growth (Big O), not as exact numbers.

When to use it, and when not to

Good fit

  • Sorting arrays in memory when average speed matters more than a guaranteed worst case. It sorts in place and scans memory sequentially, which modern CPU caches reward.
  • Inside library sorts: Java's Arrays.sort for primitive arrays uses a dual-pivot quick sort, and most C++ std::sort implementations use introsort, a quick sort that switches to heap sort if recursion gets too deep.
  • Finding the k-th smallest value: the partition step on its own gives quickselect, which runs in O(n) on average.

Pick something else when

  • You need a stable sort, where equal keys keep their original order. Use merge sort or your language's built-in stable sort.
  • You need a hard O(n log n) guarantee, for example on input an attacker controls. Use merge sort, heap sort or introsort.
  • You are sorting a linked list. Without random access, merge sort is the natural fit.

Common mistakes and bugs

  1. 1.Mixing up Hoare and Lomuto recursion

    Lomuto returns the pivot's final index, so it recurses on (lo, p − 1) and (p + 1, hi). Hoare returns a split point, not the pivot's position, so it must recurse on (lo, p) and (p + 1, hi). Using Lomuto's bounds with Hoare's partition can leave values unsorted.

  2. 2.Using the last element as the pivot with Hoare

    With pivot = a[hi], Hoare's partition can return hi itself, so quick_sort(a, lo, hi) calls itself on the same range forever. Use the middle element, rounded down, or a[lo].

  3. 3.Writing <= instead of < in the scans

    If i keeps moving while a[i] <= pivot, nothing stops it when the pivot is the largest value, and it runs off the end of the array. The strict comparisons are what keep both pointers in bounds.

  4. 4.A first or last pivot on sorted data

    Picking a[lo] or a[hi] as the pivot turns already-sorted input into the O(n²) worst case, with recursion n levels deep. In Python, a sorted list of just over 1,000 values is enough to hit the default recursion limit.

  5. 5.Assuming it is stable

    Partitioning swaps values across long distances, so two records with the same key can swap order. If you sort by a second key after a first, use a stable sort.

Interview questions

Try answering before you open the model answer.

Q1 What is the worst case of quick sort, and when does it happen?

Model answer: O(n²). It happens when partitions are maximally lopsided, for example a first- or last-element pivot on input that is already sorted. Avoid it with a middle or random pivot, median-of-three, or an introsort-style fallback to heap sort when recursion gets too deep.

Q2 How do the Lomuto and Hoare partition schemes differ?

Model answer: Lomuto uses one scanning pointer and the last element as pivot; the pivot ends at its final index. It is simpler but does more swaps and degrades on duplicates. Hoare scans from both ends, swaps less, handles duplicates well, but returns a split point rather than the pivot's position.

Q3 Is quick sort stable? Can you make it stable?

Model answer: No. Long-distance swaps can reorder equal keys. You can make it stable by partitioning into new lists (costs O(n) extra memory) or by sorting (key, original index) pairs, but both give up the in-place advantage, so a stable merge sort is usually the better answer.

Q4 Find the k-th smallest element of an unsorted array in average O(n).

Model answer: Quickselect: partition once, then recurse only into the side that contains position k. Each step discards a fraction of the array on average, so the total is O(n) on average and O(n²) in the worst case. Median-of-medians pivots make the worst case O(n).

Q5 Why is quick sort often faster than merge sort in practice, when both are O(n log n)?

Model answer: It sorts in place, so it skips merge sort's copying into an O(n) buffer, and its inner loop is tight and scans memory sequentially, which is cache-friendly. Merge sort wins when you need stability, a guaranteed worst case, linked lists, or data on disk.

Frequently asked questions

Is quick sort faster than merge sort?

On arrays in memory, usually yes. Both average O(n log n), but quick sort sorts in place and avoids copying values into a buffer, so it tends to run faster. Merge sort is the safer choice when you need a stable sort, a guaranteed O(n log n) worst case, or are sorting a linked list.

Why does this visualizer use the middle element as the pivot?

A middle pivot avoids the classic worst case on sorted and reverse-sorted input, where a first or last pivot makes quick sort quadratic. It also works correctly with Hoare's partition, which can loop forever if the pivot is the last element. Random pivots are another common choice.

What is the time complexity of quick sort?

Best and average case are O(n log n): balanced splits give about log n levels of roughly n comparisons each. The worst case is O(n²), when every pivot is the smallest or largest value in its range. Extra space is O(log n) on average, for the recursion stack.

Does quick sort work with duplicate values?

Yes, but the partition scheme matters. Hoare's scheme, used here, stops on values equal to the pivot from both sides and swaps them, so even an all-equal array splits near the middle. Lomuto's scheme sends equal values to one side and becomes O(n²) when everything is equal.

Which sort do Python, Java and JavaScript use internally?

Python's sorted() and list.sort() use Timsort, a merge sort hybrid. Java's Arrays.sort uses a dual-pivot quick sort for primitive arrays and Timsort for objects. JavaScript engines must sort stably since ES2019; V8 uses Timsort. In real code, call the built-in sort rather than your own quick sort.

Crio Software Development

Go from watching algorithms to using them

Crio's Software Development Fellowship has you practise data structures and algorithms by building real projects, the way they come up at work and in interviews. Start with a free trial session.

Explore the program

Free trial · No credit card required

Sources

  1. Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (3rd ed., MIT Press, 2009)
    Chapter 7, Quicksort; Problem 7-1 covers Hoare's partition.
  2. C. A. R. Hoare, "Quicksort", The Computer Journal 5(1), 1962
    The original paper.
  3. Sedgewick and Wayne, Algorithms (4th ed., Addison-Wesley, 2011)
    Section 2.3, Quicksort.

The animation, the worked example and the step counts are all generated by one implementation of quick sort, which is unit-tested against an independent version on edge cases and hundreds of random inputs. The Python, Java and JavaScript code is the exact code shown above, run on the same cases.

Last updated:

More algorithms, visualized

Every page runs real, tested code and lets you step through it with your own input.

All algorithms