← Back to DSA Animator
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).