Quick Sort Visualizer: Step-by-Step Animation & Complexity

Quick Sort

Category: Sorting | Time: O(n log n) | Space: O(log n)

Input Data

Visualization

Visual representation of the data structure

About Quick Sort

An efficient, in-place, comparison-based sorting algorithm. It applies the divide-and-conquer strategy. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Code Editor

The code is for reference. Editing it won't affect the visualization.

function quickSort(arr, low, high) {
  if (low < high) {
    let pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr, low, high) {
  let pivot = arr[high];
  let i = (low - 1);
  for (let j = low; j <= high - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return (i + 1);
}

Variable State

{
  "arr": "[10, 7, 8, 9, 1, 5]",
  "low": 0,
  "high": 5
}

Quick Sort: How It Works

Last updated October 28, 2026

Overview

Quick Sort picks one element as a pivot and partitions the array so that everything smaller than the pivot ends up on its left and everything else on its right. The pivot is then in its final position, and the two sides are sorted recursively.

The version on this page uses the Lomuto partition scheme with the last element as the pivot. Index i marks the end of the 'smaller than pivot' region; whenever arr[j] < pivot, that region grows by one and arr[j] is swapped into it. A final swap places the pivot just after the region.

With the default input 10, 7, 8, 9, 1, 5, the first pivot is 5: only 1 is smaller, so after partitioning the array becomes 1, 5, 8, 9, 10, 7, with 5 fixed at index 1.

Step by step

Choose the pivot (arr[high] here).
Set i = low - 1; for each j from low to high - 1, if arr[j] < pivot, increment i and swap arr[i] with arr[j].
Swap the pivot into position i + 1; this is its final index.
Recursively sort low..i and i + 2..high.
Stop when a range has fewer than two elements.

Complexity

Case	Cost	Why
Best case	O(n log n)	Each pivot splits its range roughly in half.
Average case	O(n log n)	Random pivots give balanced-enough splits on average.
Worst case	O(n^2)	With a last-element pivot, already-sorted input produces splits of size n-1 and 0 every time.
Extra space	O(log n)	Recursion stack for balanced splits; O(n) in the worst case.

When to use it

General-purpose in-memory sorting of arrays; its tight inner loop and cache-friendly access make it fast in practice.
When stability is not required and extra O(n) memory for Merge Sort is unwanted.
As the main engine of Intro Sort, which adds a fallback for the worst case.

Common mistakes

A fixed first- or last-element pivot degrades to O(n^2) on sorted or reverse-sorted input. Median-of-three or a random pivot fixes this.
Many duplicate keys also hurt Lomuto partitioning; three-way partitioning (Dutch national flag) handles them well.
Recursing on the larger side first can overflow the stack; recurse on the smaller side and loop on the larger one.

Worked Example: Quick Sort Dry Run

Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Quick Sort: follow each row, predict the next one, and compare. The run below takes 75 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.

Input: 10, 7, 8, 9, 1, 5
Result: return value = [1, 5, 7, 8, 9, 10]

Step	Line	Array	What happens
1	1	[10, 7, 8, 9, 1, 5]	low = 0, high = 5
2	2	[10, 7, 8, 9, 1, 5]	low = 0, high = 5, condition = 0 < 5
7	15	[10, 7, 8, 9, 1, 5]	low = 0, high = 5, pivot = 5, i = -1, j = 0, condition = 10 < 5
9	15	[10, 7, 8, 9, 1, 5]	low = 0, high = 5, pivot = 5, i = -1, j = 1, condition = 7 < 5
11	15	[10, 7, 8, 9, 1, 5]	low = 0, high = 5, pivot = 5, i = -1, j = 2, condition = 8 < 5
13	15	[10, 7, 8, 9, 1, 5]	low = 0, high = 5, pivot = 5, i = -1, j = 3, condition = 9 < 5
15	15	[10, 7, 8, 9, 1, 5]	low = 0, high = 5, pivot = 5, i = -1, j = 4, condition = 1 < 5
17	17	[1, 7, 8, 9, 10, 5]	low = 0, high = 5, pivot = 5, i = 0, j = 4
18	20	[1, 5, 8, 9, 10, 7]	low = 0, high = 5, pivot = 5, i = 0
19	21	[1, 5, 8, 9, 10, 7]	low = 0, high = 5, return value = 1
23	2	[1, 5, 8, 9, 10, 7]	low = 0, high = 0, condition = 0 < 0
26	2	[1, 5, 8, 9, 10, 7]	low = 2, high = 5, condition = 2 < 5
31	15	[1, 5, 8, 9, 10, 7]	low = 2, high = 5, pivot = 7, i = 1, j = 2, condition = 8 < 7
33	15	[1, 5, 8, 9, 10, 7]	low = 2, high = 5, pivot = 7, i = 1, j = 3, condition = 9 < 7
35	15	[1, 5, 8, 9, 10, 7]	low = 2, high = 5, pivot = 7, i = 1, j = 4, condition = 10 < 7
36	20	[1, 5, 7, 9, 10, 8]	low = 2, high = 5, pivot = 7, i = 1
37	21	[1, 5, 7, 9, 10, 8]	low = 2, high = 5, return value = 2
41	2	[1, 5, 7, 9, 10, 8]	low = 2, high = 1, condition = 2 < 1
44	2	[1, 5, 7, 9, 10, 8]	low = 3, high = 5, condition = 3 < 5
49	15	[1, 5, 7, 9, 10, 8]	low = 3, high = 5, pivot = 8, i = 2, j = 3, condition = 9 < 8
51	15	[1, 5, 7, 9, 10, 8]	low = 3, high = 5, pivot = 8, i = 2, j = 4, condition = 10 < 8
52	20	[1, 5, 7, 8, 10, 9]	low = 3, high = 5, pivot = 8, i = 2
53	21	[1, 5, 7, 8, 10, 9]	low = 3, high = 5, return value = 3
57	2	[1, 5, 7, 8, 10, 9]	low = 3, high = 2, condition = 3 < 2
60	2	[1, 5, 7, 8, 10, 9]	low = 4, high = 5, condition = 4 < 5
65	15	[1, 5, 7, 8, 10, 9]	low = 4, high = 5, pivot = 9, i = 3, j = 4, condition = 10 < 9
66	20	[1, 5, 7, 8, 9, 10]	low = 4, high = 5, pivot = 9, i = 3
67	21	[1, 5, 7, 8, 9, 10]	low = 4, high = 5, return value = 4
71	2	[1, 5, 7, 8, 9, 10]	low = 4, high = 3, condition = 4 < 3
74	2	[1, 5, 7, 8, 9, 10]	low = 5, high = 5, condition = 5 < 5
75	8	[1, 5, 7, 8, 9, 10]	return value = [1, 5, 7, 8, 9, 10]

Frequently Asked Questions

About Quick Sort

What is Quick Sort?

Quick Sort is a highly efficient, comparison-based, divide-and-conquer sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

What is the time complexity of Quick Sort?

The average-case time complexity is an excellent O(n log n). However, its worst-case time complexity is O(n^2), which occurs if the pivot selection consistently leads to unbalanced partitions (e.g., always picking the smallest or largest element).

Is Quick Sort an in-place algorithm?

Yes, Quick Sort is typically implemented as an in-place algorithm. It doesn't need an auxiliary array for the data, but it does require O(log n) space on average for the recursion stack.

Is Quick Sort stable?

No, the standard implementation of Quick Sort is not stable. The partitioning step can change the relative order of elements with equal values as it swaps elements across the pivot.

How does the choice of pivot affect performance?

Pivot selection is critical. A good pivot (one that is close to the median) results in balanced partitions and O(n log n) performance. A bad pivot results in unbalanced partitions and degrades performance towards O(n^2).

What are common pivot selection strategies?

Common strategies include: 1) Always picking the first or last element (simple but vulnerable to worst-case scenarios). 2) Picking a random element (generally safe). 3) Using the 'median-of-three' method, which takes the median of the first, middle, and last elements to avoid worst-case on sorted/reverse-sorted data.

What is the Lomuto partition scheme?

The Lomuto partition scheme, which is visualized here, typically chooses the last element as the pivot. It maintains an index for the boundary of the 'less than pivot' section and swaps elements into place. It's simple to implement but can be less efficient than other schemes like Hoare's.

When would you not use Quick Sort?

You might avoid Quick Sort in applications where a worst-case guarantee of O(n log n) is required. It's also not stable, so if preserving the order of equal elements is important, Merge Sort would be a better choice.

What is a dual-pivot Quick Sort?

This is a variation that uses two pivots to partition the array into three sub-arrays: elements less than the first pivot, elements between the pivots, and elements greater than the second pivot. This can be faster in practice and is used in Java's standard library.

Can Quick Sort be implemented iteratively?

Yes, Quick Sort can be implemented iteratively using an explicit stack to manage the sub-array boundaries. This avoids deep recursion and potential stack overflow errors for very large arrays.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.

Kth Largest Element in an Array

From: Google

View Question