The Quick Sort algorithm sorts an array by picking a pivot, partitioning the other items around it, and repeating on the smaller parts. Use the visualization below to run it, pause it, step through it, and even step backward.
Operation log
Recursive calls
Introduction to Quick Sort
Quick Sort is a comparison-based sorting algorithm and one of the best-known divide and conquer algorithms. Developers use it because it is simple, sorts in place, and is fast on many real inputs. Its key idea is partitioning: rearrange items so the pivot lands in its final position, with items that belong before it on one side and items that belong after it on the other. Learning Quick Sort is a great way to understand sorting algorithms and recursion.
What Is the Quick Sort Algorithm?
The Quick Sort algorithm sorts an array by choosing one element, the pivot, and partitioning the rest around it. After partitioning, the pivot never moves again. Quick Sort then sorts the left part and the right part the same way. Take [3, 1, 2]. With pivot 2, the value 1 goes left and 3 stays right, giving [1, 2, 3]. Each step shrinks the problem until pieces are too small to need sorting.
How Quick Sort Works Step by Step
- Choose a pivot.
- Partition the array around the pivot.
- Recursively sort the left subarray.
- Recursively sort the right subarray.
- Finish when each subarray has zero or one element.
The exact moves in step 2 depend on the partition scheme. This page uses the Lomuto scheme for every pivot strategy: the chosen pivot is first swapped to the end of the subarray, then partitioned. Its invariant: while scanning, items from the start up to boundary i hold values less than or equal to the pivot, and items from i up to the scan position hold values greater than the pivot. Because of the “less than or equal” rule, equal values may sit on the left, so do not assume everything on the left is strictly smaller.
Understanding the Pivot in Quick Sort
The pivot is the reference value for a partition. Pivot choice matters because it decides how even the two parts are. Common strategies:
- First element: easy, but slow on already sorted input.
- Last element: also easy and equally weak on sorted input.
- Middle element: handles sorted and reverse-sorted arrays well. Note that the middle index is not the median value.
- Random element: makes consistently bad splits unlikely.
- Median of three (optional): use the median of the first, middle and last values for better balance.
Try each strategy in the visualization on a sorted array and compare the comparison counts.
Quick Sort Example With a Step-by-Step Walkthrough
Array [8, 3, 1, 7, 0, 10, 2], Lomuto partition, last element as pivot.
- Pivot is 2, boundary i = 0. Scan: 8 and 3 are greater than 2, so nothing moves.
- 1 is at most 2, so swap it with index 0: [1, 3, 8, 7, 0, 10, 2], i = 1.
- 7 is greater. 0 is at most 2, so swap with index 1: [1, 0, 8, 7, 3, 10, 2], i = 2. 10 is greater.
- Place the pivot: swap index 2 with the end: [1, 0, 2, 7, 3, 10, 8]. The 2 is final.
- Left part [1, 0], pivot 0: nothing is smaller, so swap 1 and 0 to get [0, 1].
- Right part [7, 3, 10, 8], pivot 8: 7 and 3 stay in the left group, 10 is greater, then swap 10 and 8: [7, 3, 8, 10].
- Sort [7, 3] with pivot 3: swap to [3, 7].
The final array is [0, 1, 2, 3, 7, 8, 10].
Quick Sort Pseudocode
quickSort(A, lo, hi):
if lo >= hi: return // base case
p = partition(A, lo, hi)
quickSort(A, lo, p - 1)
quickSort(A, p + 1, hi)
partition(A, lo, hi): // pivot = A[hi]
i = lo
for j = lo to hi - 1:
if A[j] <= A[hi]: swap A[i], A[j]; i = i + 1
swap A[i], A[hi]
return i // pivot's final index
The base case stops recursion on zero or one element. The partition function returns the pivot’s final index, which the recursive calls use to exclude it.
Quick Sort Implementation in JavaScript
function quickSort(input) {
const a = [...input]; // copy: input is not modified
const sort = (lo, hi) => {
if (lo >= hi) return; // handles [] and [x]
const p = partition(lo, hi);
sort(lo, p - 1);
sort(p + 1, hi);
};
const partition = (lo, hi) => {
const pivot = a[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (a[j] <= pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; }
}
[a[i], a[hi]] = [a[hi], a[i]];
return i;
};
sort(0, a.length - 1);
return a;
}
The function copies the input, so the original stays unchanged. The partition loop moves small values to the left of boundary i, and the final swap puts the pivot in place. For other pivot strategies, swap the chosen element to index hi first.
Time Complexity of Quick Sort
Quick Sort time complexity depends on partition balance. When partitions are roughly even, there are about log n levels and each level does O(n) work, so time is O(n log n). If every partition is extremely lopsided, such as a sorted array with a first or last pivot, there are n levels and the time grows to O(n²). Random pivots make this unlikely, but the theoretical worst case still exists.
| Case | Time |
|---|---|
| Best | O(n log n) |
| Average | O(n log n) |
| Worst | O(n²) |
Space Complexity of Quick Sort
Quick Sort space complexity has two parts. The array itself is the input, and partitioning rearranges it in place without a second array. But recursive calls use stack memory. With balanced splits the depth is about log n, so O(log n); with badly unbalanced splits it can reach O(n). In-place partitioning is not the same as zero extra memory.
Advantages of Quick Sort
- Strong average-case performance.
- Often fast in practice because it works well with memory caches.
- In-place partitioning in common implementations.
- Low auxiliary memory compared with array-based Merge Sort.
- Suitable for many general-purpose sorting tasks, though not always the fastest option.
Disadvantages of Quick Sort
- Worst-case O(n²) time.
- Sensitive to pivot selection.
- Recursive stack can grow deep.
- Common versions are not stable.
- Can be wasteful on tiny arrays unless a simpler method such as insertion sort handles them.
Quick Sort vs Merge Sort
| Feature | Quick Sort | Merge Sort |
|---|---|---|
| Average time | O(n log n) | O(n log n) |
| Worst time | O(n²) | O(n log n) |
| Auxiliary space | O(log n) typical stack | O(n) for arrays |
| Stable | Usually no | Yes |
| In place | Yes (array version) | Not in the usual array version |
| Typical use | In-memory arrays, memory-sensitive work | Stable sorts, linked lists, external data |
Choose Merge Sort when stability or guaranteed worst-case time matters. Details vary by implementation.
Common Applications of Quick Sort
Quick Sort is used to sort in-memory data in libraries and programs, and some standard libraries use variants of it, though not every language does. Its partitioning idea also powers other algorithms, such as Quickselect, which finds the k-th smallest item without a full sort.
Common Mistakes When Implementing Quick Sort
- Wrong partition boundaries.
- Missing base cases, which cause infinite recursion.
- Wrong recursive ranges, such as including the pivot again.
- Mishandling duplicates.
- Confusing the pivot’s final index with its original index.
- Using a pivot strategy that does not match the partition code.
- Assuming stability.
- Not testing sorted and reverse-sorted arrays.
Frequently Asked Questions About Quick Sort
What is Quick Sort in simple words?
It picks a pivot, splits the items around it, then sorts each side the same way.
Why is Quick Sort called a divide-and-conquer algorithm?
It divides the array by partitioning and conquers each smaller part recursively.
What is the pivot in Quick Sort?
The value used as the reference when partitioning. After partitioning it sits in its final place.
What is the average time complexity of Quick Sort?
O(n log n).
What is the worst-case time complexity of Quick Sort?
O(n²), when partitions are repeatedly very unbalanced.
Is Quick Sort an in-place sorting algorithm?
Array versions are in place, but recursion still uses stack memory.
Is Quick Sort stable?
Common versions, including this one, are not stable.
When should I use Quick Sort instead of Merge Sort?
When sorting arrays in memory, memory is limited, and stability is not required.
How does pivot selection affect Quick Sort performance?
Pivots that split evenly give O(n log n). Pivots near the minimum or maximum cause slow, lopsided splits.
Can Quick Sort handle duplicate values?
Yes. This page’s version uses a “less than or equal” rule. Three-way partitioning is faster when many values repeat.
Conclusion
Quick Sort works by partitioning around a pivot and recursing on smaller parts. Partitioning does the real work, and pivot choice controls speed. Scroll back to the visualization and try different arrays and pivot strategies to see this yourself.