Imagine you're arranging students in a line by height. Instead of comparing everyone with everyone, you pick one student, say Rahul, and tell the class:
"Everyone shorter than Rahul, stand on his left.
Everyone taller than Rahul, stand on his right."After this one instruction, Rahul is standing in exactly the right spot. He never needs to move again. Now you repeat the same trick separately on the left group and the right group.
That's Quick Sort.
Quick Sort is a divide-and-conquer sorting algorithm that picks a pivot element, partitions the array so that smaller elements go to the left of the pivot and larger elements go to the right, and then recursively sorts the two parts.
Quick Sort is one of the most widely used sorting algorithms. It sorts in place, it is very fast in practice, and its partition idea shows up in many interview problems.
The Core Idea
Like Merge Sort, Quick Sort uses divide and conquer, but it splits the work differently:
Step | Merge Sort | Quick Sort |
|---|---|---|
Divide | Split at the middle index (trivial) | Partition around a pivot (real work) |
Conquer | Sort both halves recursively | Sort both parts recursively |
Combine | Merge the halves (real work) | Nothing to do |
In Merge Sort, the hard work happens after the recursive calls. In Quick Sort, it happens before them, in the partition step.
The algorithm is:
quickSort(arr, low, high):
if low < high:
p = partition(arr, low, high) // pivot lands at index p
quickSort(arr, low, p - 1) // sort the left part
quickSort(arr, p + 1, high) // sort the right partAfter partitioning, the array looks like this:
[ elements < pivot | pivot | elements ≥ pivot ]
↑
already in its final positionNotice that the left and right parts are not sorted yet. We only know that every element on the left is smaller than the pivot. Sorting each part is the job of the recursive calls.
Lomuto Partition
There are several ways to partition. The easiest one to understand is the Lomuto partition scheme:
Choose the last element as the pivot.
Keep a pointer
ithat marks the end of the "smaller than pivot" region.Scan the array with
j. Wheneverarr[j] < pivot, grow the smaller region by one and swaparr[j]into it.Finally, swap the pivot into position
i + 1.
While scanning, the array always has this shape:
[ < pivot | ≥ pivot | not checked yet | pivot ]
low i j highPartition Step by Step
Let's partition:
[10, 80, 30, 90, 40, 50, 70]
pivot = 70 (last element), i = -1j = 0: 10 < 70 → i = 0, swap arr[0] and arr[0]
[10, 80, 30, 90, 40, 50, 70]
j = 1: 80 ≥ 70 → do nothing
[10, 80, 30, 90, 40, 50, 70]
j = 2: 30 < 70 → i = 1, swap arr[1] and arr[2]
[10, 30, 80, 90, 40, 50, 70]
j = 3: 90 ≥ 70 → do nothing
[10, 30, 80, 90, 40, 50, 70]
j = 4: 40 < 70 → i = 2, swap arr[2] and arr[4]
[10, 30, 40, 90, 80, 50, 70]
j = 5: 50 < 70 → i = 3, swap arr[3] and arr[5]
[10, 30, 40, 50, 80, 90, 70]The scan is done. Now place the pivot right after the smaller region, at index i + 1 = 4:
swap arr[4] and arr[6]
[10, 30, 40, 50, 70, 90, 80]
\____________/ ↑ \_____/
< 70 70 > 7070 is now in its final sorted position. Quick Sort then recursively sorts [10, 30, 40, 50] and [90, 80].
Quick Sort in Java
Here's the complete program using Lomuto partition. It prints the array after every partition.
import java.util.Arrays;
class Main {
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int p = partition(arr, low, high);
quickSort(arr, low, p - 1); // left of pivot
quickSort(arr, p + 1, high); // right of pivot
}
}
// Lomuto partition: last element is the pivot
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1; // end of the "smaller than pivot" region
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high); // put pivot in its final place
System.out.println("Pivot " + pivot + " -> index " + (i + 1)
+ ": " + Arrays.toString(arr));
return i + 1;
}
static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String[] args) {
int[] arr = {10, 80, 30, 90, 40, 50, 70};
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted: " + Arrays.toString(arr));
}
}Output:
Pivot 70 -> index 4: [10, 30, 40, 50, 70, 90, 80]
Pivot 50 -> index 3: [10, 30, 40, 50, 70, 90, 80]
Pivot 40 -> index 2: [10, 30, 40, 50, 70, 90, 80]
Pivot 30 -> index 1: [10, 30, 40, 50, 70, 90, 80]
Pivot 80 -> index 5: [10, 30, 40, 50, 70, 80, 90]
Sorted: [10, 30, 40, 50, 70, 80, 90]Look at the left part [10, 30, 40, 50]. It was already sorted, so the last element was always the largest. Each partition only removed one element (50, then 40, then 30). Keep this in mind, because it is exactly what causes Quick Sort's worst case.
Time Complexity
Partitioning a range of n elements scans it once, so it takes O(n). The total time depends on how evenly the pivot splits the array.
Best Case: Pivot Splits in the Middle
n
/ \
n/2 n/2
/ \ / \
n/4 n/4 n/4 n/4
...This is the same shape as Merge Sort: log n levels with O(n) work per level.
T(n) = 2 T(n/2) + O(n) → O(n log n)Worst Case: Pivot Is Always the Smallest or Largest
If the array is already sorted and we always pick the last element, the pivot is always the maximum. One side gets n - 1 elements and the other side gets nothing:
n
\
n-1
\
n-2
\
...
\
1Work = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 → O(n²)Average Case
On random data, the pivot usually lands somewhere reasonable. Even a consistently lopsided split like 10% / 90% still gives O(log n) levels, so the average is:
O(n log n)Seeing the Difference
Let's count the comparisons Quick Sort (last-element pivot) makes on 1,000 numbers, first shuffled and then already sorted:
import java.util.Random;
class Main {
static long comparisons;
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int p = partition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}
}
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
comparisons++;
if (arr[j] < pivot) {
i++;
int t = arr[i]; arr[i] = arr[j]; arr[j] = t;
}
}
int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t;
return i + 1;
}
public static void main(String[] args) {
int n = 1000;
int[] sorted = new int[n];
for (int i = 0; i < n; i++) sorted[i] = i;
int[] shuffled = sorted.clone();
Random rnd = new Random(42);
for (int i = n - 1; i > 0; i--) { // Fisher-Yates shuffle
int j = rnd.nextInt(i + 1);
int t = shuffled[i]; shuffled[i] = shuffled[j]; shuffled[j] = t;
}
comparisons = 0;
quickSort(shuffled, 0, n - 1);
System.out.println("Shuffled input: " + comparisons + " comparisons");
comparisons = 0;
quickSort(sorted, 0, n - 1);
System.out.println("Sorted input: " + comparisons + " comparisons");
}
}Output:
Shuffled input: 11482 comparisons
Sorted input: 499500 comparisonsThe sorted input needs exactly 1000 × 999 / 2 = 499,500 comparisons, more than 40 times the shuffled case. (Using a fixed seed 42 makes the shuffle, and therefore the output, the same on every run.)
Case | Time | When it happens |
|---|---|---|
Best |
| Pivot always near the median |
Average |
| Random data or random pivot |
Worst |
| Pivot always the min or max (e.g. sorted input with first/last pivot) |
Space Complexity
Quick Sort partitions in place, so it doesn't need a temporary array like Merge Sort. The only extra memory is the recursion call stack:
Balanced splits → recursion depth O(log n) → O(log n) space
Worst case → recursion depth O(n) → O(n) spaceThat worst-case depth is a real problem in Java. Running the simple version above on an already sorted array of just a few tens of thousands of elements can throw a StackOverflowError with default JVM settings. We'll fix this below.
Quick Sort Is Not Stable
Partitioning swaps elements across long distances, so equal elements can change their relative order.
For example, partitioning [5a, 5b, 1] with pivot 1 swaps 1 with 5a:
Before: [5a, 5b, 1]
After: [1, 5b, 5a]5a and 5b are equal but their order has flipped. That's why Java uses a merge-based sort (TimSort), not Quick Sort, when sorting objects, where stability matters.
Choosing a Better Pivot
The worst case happens when the pivot is consistently a bad choice. Common fixes:
1. Random Pivot
Pick a random index, swap it to the end, and partition as usual.
import java.util.Arrays;
import java.util.Random;
class Main {
static final Random random = new Random();
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int p = randomizedPartition(arr, low, high);
quickSort(arr, low, p - 1);
quickSort(arr, p + 1, high);
}
}
static int randomizedPartition(int[] arr, int low, int high) {
// Pick a random index in [low, high] and move it to the end
int r = low + random.nextInt(high - low + 1);
swap(arr, r, high);
return partition(arr, low, high); // normal Lomuto
}
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}Output:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]The input here is already sorted, the classic worst case for a fixed last-element pivot. With a random pivot, no particular input is consistently bad. The worst case is still O(n²) in theory, but its probability is tiny, and the expected running time is O(n log n) for every input.
2. Median of Three
Look at the first, middle and last elements and use the median of the three as the pivot. For sorted or reverse-sorted input, this picks the true middle element instead of the minimum or maximum, so the splits stay balanced.
[1, 2, 3, 4, 5, 6, 7, 8, 9]
↑ ↑ ↑
1 5 9 → median = 5Hoare Partition
The original partition scheme, invented by Tony Hoare (who created Quick Sort in 1959), uses two pointers moving toward each other:
imoves right until it finds an element≥ pivot.jmoves left until it finds an element≤ pivot.If they haven't crossed, swap them and continue.
import java.util.Arrays;
class Main {
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int p = hoarePartition(arr, low, high);
quickSort(arr, low, p); // note: p, not p - 1
quickSort(arr, p + 1, high);
}
}
// Hoare partition: first element is the pivot
static int hoarePartition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low - 1;
int j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j) {
return j;
}
swap(arr, i, j);
}
}
static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String[] args) {
int[] arr = {10, 80, 30, 90, 40, 50, 70};
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}Output:
[10, 30, 40, 50, 70, 80, 90]Two important differences from Lomuto:
Hoare returns a split point
j, not the pivot's final position. Everything inlow..jis≤ pivotand everything inj+1..highis≥ pivot. That's why the recursive call isquickSort(arr, low, p), notp - 1.Hoare does about three times fewer swaps on average and handles many duplicates much better, which is why it is usually faster in practice.
Property | Lomuto | Hoare |
|---|---|---|
Pivot in this code | Last element | First element |
Returns | Pivot's final index | A split point |
Recursive calls |
|
|
Swaps | More | Fewer |
All-equal array |
|
|
Ease of understanding | Easier | Trickier |
Handling Many Duplicates: 3-Way Partition
What if the array is something like [4, 4, 4, 4, 4, ...]? With Lomuto, every element equal to the pivot ends up on one side, so the splits become completely lopsided and the time becomes O(n²).
The fix is 3-way partitioning (also called the Dutch National Flag partition). It splits the range into three groups:
[ < pivot | == pivot | > pivot ]
lt gtThe middle group is already in its final place, so we recurse only on the left and right groups.
import java.util.Arrays;
class Main {
static void quickSort3Way(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int pivot = arr[low];
int lt = low; // arr[low..lt-1] < pivot
int i = low; // arr[lt..i-1] == pivot
int gt = high; // arr[gt+1..high] > pivot
while (i <= gt) {
if (arr[i] < pivot) {
swap(arr, lt, i);
lt++;
i++;
} else if (arr[i] > pivot) {
swap(arr, i, gt);
gt--; // i stays: the value swapped in is not checked yet
} else {
i++;
}
}
quickSort3Way(arr, low, lt - 1);
quickSort3Way(arr, gt + 1, high);
}
static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String[] args) {
int[] arr = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4};
quickSort3Way(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}Output:
[1, 1, 4, 4, 4, 4, 4, 4, 4, 4, 9, 9, 9]In the first partition, all eight 4s are placed at once and never touched again. This same three-pointer idea solves the famous Sort Colors problem (sort an array of 0s, 1s and 2s in one pass).
Limiting the Stack: Recurse on the Smaller Side
We can guarantee O(log n) stack space, even in the worst case, with a simple trick: make a recursive call only for the smaller part, and handle the larger part with a loop.
static void quickSort(int[] arr, int low, int high) {
while (low < high) {
int p = partition(arr, low, high);
if (p - low < high - p) {
quickSort(arr, low, p - 1); // smaller part: recurse
low = p + 1; // larger part: loop
} else {
quickSort(arr, p + 1, high); // smaller part: recurse
high = p - 1; // larger part: loop
}
}
}Each recursive call handles at most half of the current range, so the depth can never exceed log₂ n. The time is still O(n²) in the worst case, but the program will no longer crash with a StackOverflowError.
Bonus: Quickselect
Partition puts the pivot at its final sorted index. We can use this to find the k-th smallest element without fully sorting.
After partitioning:
p == k - 1 → the pivot is the answer
p > k - 1 → the answer is in the left part
p < k - 1 → the answer is in the right partUnlike Quick Sort, we only recurse into one side.
class Main {
// Returns the k-th smallest element (k is 1-based)
static int quickSelect(int[] arr, int low, int high, int k) {
int p = partition(arr, low, high);
if (p == k - 1) {
return arr[p];
} else if (p > k - 1) {
return quickSelect(arr, low, p - 1, k); // go left only
} else {
return quickSelect(arr, p + 1, high, k); // go right only
}
}
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String[] args) {
int[] arr = {7, 10, 4, 3, 20, 15};
int n = arr.length;
System.out.println("3rd smallest: "
+ quickSelect(arr.clone(), 0, n - 1, 3));
// k-th largest = (n - k + 1)-th smallest
System.out.println("2nd largest: "
+ quickSelect(arr.clone(), 0, n - 1, n - 2 + 1));
}
}Output:
3rd smallest: 7
2nd largest: 15The sorted array would be [3, 4, 7, 10, 15, 20], so both answers are correct.
Because we only follow one side, the average work is n + n/2 + n/4 + ... ≈ 2n:
Quickselect average → O(n)
Quickselect worst → O(n²) (use a random pivot to avoid it in practice)That beats sorting first, which costs O(n log n).
Common Mistakes
1. Mixing up Lomuto and Hoare recursion ranges
With Lomuto, use (low, p - 1) and (p + 1, high). With Hoare, use (low, p) and (p + 1, high). Using Lomuto's ranges with Hoare's partition can skip elements or leave the array unsorted, and using (low, p) with Lomuto can recurse forever.
2. Wrong base case
The condition must be if (low < high). Without it, the recursion has no stopping point: partition() gets called on empty ranges like (0, -1), reads an invalid index such as arr[-1], and the program crashes.
3. Forgetting the final pivot swap in Lomuto
Without swap(arr, i + 1, high), the pivot stays at the end and the returned index is wrong.
4. Using a fixed first/last pivot on sorted data
This is the classic way to hit O(n²) time and a stack overflow. Use a random pivot or median of three.
5. Assuming Quick Sort is stable
It is not. If you need stability, use Merge Sort.
Quick Sort vs Merge Sort
Property | Quick Sort | Merge Sort |
|---|---|---|
Average time |
|
|
Worst time |
|
|
Extra space |
|
|
In-place | Yes | No (for arrays) |
Stable | No | Yes |
Where the work happens | Before recursion (partition) | After recursion (merge) |
Practical speed on arrays | Usually faster (cache friendly, no copying) | Slightly slower |
Best for | Primitive arrays in memory | Linked lists, stable sorts, external sorting |
What Java Actually Uses
Arrays.sort(int[])and other primitive arrays use Dual-Pivot Quicksort (by Vladimir Yaroslavskiy, Jon Bentley and Joshua Bloch). It uses two pivots to split the array into three parts. The current Java documentation states that it offersO(n log n)performance on all data sets, because modern versions fall back to other techniques when the recursion gets too deep.Arrays.sort(Object[])andCollections.sort()use TimSort, a stable merge-based sort, because objects often need stability.
For primitives like int, stability doesn't matter, since two equal int values are indistinguishable.
Interview Tips and Practice
Be able to write Lomuto partition from memory and trace it on a small array.
Know exactly when the worst case happens and two ways to avoid it (random pivot, median of three).
Explain why Quick Sort is often faster than Merge Sort despite its worse worst case: in-place, fewer data copies, good cache behaviour.
For "k-th largest/smallest" questions, mention Quickselect (
O(n)average) as an alternative to sorting.
Practice problems:
Sort an Array (LeetCode 912). A plain last-element pivot may time out on sorted inputs, so try a random pivot, and use 3-way partition for arrays with many duplicates.
Sort Colors (LeetCode 75): 3-way partition
Kth Largest Element in an Array (LeetCode 215): Quickselect
K Closest Points to Origin (LeetCode 973): Quickselect on distances
Move all negative numbers to one side of the array: a single partition pass
The Main Idea
Quick Sort picks a pivot, partitions the array around it, and recursively sorts the two sides.
Pick a pivot
↓
Partition: smaller left, larger right
↓
Pivot is now in its final position
↓
Recursively sort left and right partsIts key facts:
Best / Average → O(n log n)
Worst → O(n²) (bad pivots, e.g. sorted input + last-element pivot)
Space → O(log n) average stack, O(n) worst
In-place → Yes
Stable → NoQuick Sort is usually the fastest general-purpose in-memory sort, as long as the pivot is chosen wisely. Its partition step is also the foundation of Quickselect and the Dutch National Flag problem.
So far, every algorithm has sorted by comparing elements. In the next chapter, we'll see Counting Sort and Radix Sort, which sort integers without comparing them at all and can beat O(n log n).