DSA AnimatorDSA animations
Quick Sort LC #912 Medium Divide & Conquer · Partition
Problem

Given an array of integers nums, sort the array in ascending order using the Quick Sort algorithm — pick a pivot element, partition the array so that all elements smaller than the pivot land to its left and all elements greater land to its right, then recursively sort each side.

Example 1
Input: nums = [8,4,3,7,6]
Output: [3,4,6,7,8]
Constraints: 1 ≤ n ≤ 5*10^4  |  -5*10^4 ≤ nums[i] ≤ 5*10^4
Try Examples
Custom:
Approach
Partition Around a Pivot, Recurse
Pick the last element of a range as pivot, partition so smaller values move left and larger values stay right of it, then recursively quicksort each side. Every pivot lands in its final sorted index the moment it's placed. Avg O(n log n) time — but O(n²) worst case on already-sorted input, since a last-element pivot then splits off only one element per call.
Array
Pivot Comparing Swapping Sorted
nums[] — current state
Variables
range [lo,hi]
—
boundary i
—
comparisons
0
swaps
0
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Pick pivot = last element of the range
2
Partition: walk j through the range, swap smaller-than-pivot elements to the left boundary
3
Swap pivot into its final position (boundary+1)
4
Recursively quicksort the left and right subranges
Avg
O(n log n)
Worst
O(n²)
Space
O(log n)
Why It Works

After a partition step completes, the pivot is guaranteed to sit in its final sorted position — every element to its left is ≤ the pivot and every element to its right is ≥ the pivot. That means recursion never needs to revisit that index again; each recursive call only has to solve the strictly smaller left and right subranges, until ranges shrink to 0 or 1 elements (already sorted by definition).

How to solve Quick Sort

LeetCode 912 · Medium · Sorting Algorithms · Pattern: Partition + Recursion

Why the obvious approach is slow

Simple sorts compare almost every pair, which is O(n²). Quick sort divides the problem instead.

The key idea

Pick a pivot, here the last element. Partition: move everything smaller than the pivot to the left side. Then put the pivot right after them, which is its final sorted position. Now sort the left part and the right part recursively. Each partition is one linear scan.

Remember

Partition puts the pivot in its final place. Choose pivots well to avoid the quadratic worst case.

Run the animation above on your own input, or watch the 1:48 video explanation of Quick Sort with a dry run and Java code.

More Sorting Algorithms problems