Why should you care?
Sorting is everywhere in software.
We sort:
- Numbers
- Names
- Search results
- Prices
- Database records
- Files
- Scores
- Logs
In the previous article, we learned Merge Sort, which can sort an array in O(n log n) time.
Quick Sort also uses the Divide and Conquer strategy, but it approaches the problem differently.
Instead of splitting the array simply in half, Quick Sort chooses an element called a pivot and rearranges the array so that:
smaller values | pivot | larger values
Enter fullscreen mode
Exit fullscreen mode
It then recursively sorts the two sides.
Quick Sort is particularly important because it is often very fast in practice and is a fundamental sorting algorithm to understand.
The Problem
Consider:
[8, 3, 1, 7, 0, 10, 2]
Enter fullscreen mode
Exit fullscreen mode
We want:
[0, 1, 2, 3, 7, 8, 10]
Enter fullscreen mode
Exit fullscreen mode
One approach is Merge Sort:
Divide → Sort → Merge
Enter fullscreen mode
Exit fullscreen mode
Quick Sort takes another approach:
Choose pivot
↓
Partition
↓
Sort left side
↓
Sort right side
Enter fullscreen mode
Exit fullscreen mode
For example, choose:
pivot = 7
Enter fullscreen mode
Exit fullscreen mode
Rearrange the array around it:
[3, 1, 0, 2] 7 [8, 10]
Enter fullscreen mode
Exit fullscreen mode
Now 7 is in its correct final position.
We only need to sort:
[3, 1, 0, 2]
Enter fullscreen mode
Exit fullscreen mode
and:
[8, 10]
Enter fullscreen mode
Exit fullscreen mode
This is the central idea behind Quick Sort.
The Concept
Quick Sort has three main steps:
1. Choose a pivot
2. Partition the array
3. Recursively sort the partitions
Enter fullscreen mode
Exit fullscreen mode
Step 1: Choose a pivot
The pivot can be selected in several ways:
First element
Last element
Middle element
Random element
Median-based strategy
Enter fullscreen mode
Exit fullscreen mode
For a simple implementation, we can choose the last element.
Step 2: Partition
Rearrange the array so that:
values pivot
Enter fullscreen mode
Exit fullscreen mode
For example:
[6, 3, 8, 5, 2, 7, 4]
↑
pivot
Enter fullscreen mode
Exit fullscreen mode
After partitioning:
[3, 5, 2, 4] [6] [8, 7]
Enter fullscreen mode
Exit fullscreen mode
The exact arrangement can vary depending on the partition algorithm.
The important property is that elements on the left are smaller than the pivot and elements on the right are larger.
The pivot is now in its final position.
Step 3: Recursively sort
Now apply Quick Sort to the two partitions:
[3, 5, 2, 4]
Enter fullscreen mode
Exit fullscreen mode
and:
[8, 7]
Enter fullscreen mode
Exit fullscreen mode
Continue until the partitions contain zero or one element.
At that point, they are already sorted.
Simple Explanation
Imagine organizing students according to height.
Choose one student as the reference student.
Then ask everyone else to move:
Shorter students → left
Reference student → middle
Taller students → right
Enter fullscreen mode
Exit fullscreen mode
Now the reference student’s relative position is correct.
You don’t need to move that student again.
Then repeat the same process for the shorter group and taller group.
Eventually:
Shorter group
↓
sorted
Reference
↓
Taller group
↓
sorted
Enter fullscreen mode
Exit fullscreen mode
Together, everything is sorted.
That’s Quick Sort.
Real-world Analogy
Imagine arranging books by thickness.
Pick one book as the pivot.
Place:
Thinner books → left
Pivot book → middle
Thicker books → right
Enter fullscreen mode
Exit fullscreen mode
Now take the left group and repeat.
Then take the right group and repeat.
Eventually, every book ends up in the correct order.
The key idea is not that the pivot immediately sorts the entire collection.
Instead:
The pivot divides one large sorting problem into smaller sorting problems.
Code Example
Let’s implement Quick Sort in Java using the Lomuto partition scheme.
public static void quickSort(
int[] arr,
int low,
int high) {
if (low high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex – 1);
quickSort(arr, pivotIndex + 1, high);
}
}
Enter fullscreen mode
Exit fullscreen mode
Now the partition function:
public 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++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
Enter fullscreen mode
Exit fullscreen mode
We can use it like this:
public static void main(String[] args) {
int[] arr = {
8, 3, 1, 7, 0, 10, 2
};
quickSort(arr, 0, arr.length – 1);
for (int value : arr) {
System.out.print(value + ” “);
}
}
Enter fullscreen mode
Exit fullscreen mode
Output:
0 1 2 3 7 8 10
Enter fullscreen mode
Exit fullscreen mode
Understanding Partition
This is the most important part of Quick Sort.
Consider:
[4, 2, 7, 3, 1, 6]
Enter fullscreen mode
Exit fullscreen mode
Suppose:
pivot = 6
Enter fullscreen mode
Exit fullscreen mode
We want:
[values ≤ 6] 6 [values > 6]
Enter fullscreen mode
Exit fullscreen mode
The partition algorithm scans the array.
Whenever it finds a value smaller than or equal to the pivot, it moves that value toward the left partition.
Eventually we get something like:
[4, 2, 3, 1] 6 [7]
Enter fullscreen mode
Exit fullscreen mode
The pivot is now correctly positioned.
We then recursively sort:
[4, 2, 3, 1]
Enter fullscreen mode
Exit fullscreen mode
and:
[7]
Enter fullscreen mode
Exit fullscreen mode
The right side is already sorted.
Why Does Quick Sort Work?
The most important observation is:
Once the pivot is placed correctly, it never needs to move again.
Suppose:
[4, 2, 1, 3, 8, 7, 5]
Enter fullscreen mode
Exit fullscreen mode
Choose:
pivot = 5
Enter fullscreen mode
Exit fullscreen mode
After partitioning:
[4, 2, 1, 3] 5 [8, 7]
Enter fullscreen mode
Exit fullscreen mode
Everything on the left belongs before 5.
Everything on the right belongs after 5.
Therefore, the original problem:
Sort 7 elements
Enter fullscreen mode
Exit fullscreen mode
becomes:
Sort 4 elements
+
Sort 2 elements
Enter fullscreen mode
Exit fullscreen mode
The pivot itself is already finished.
This process continues recursively.
Time Complexity
Quick Sort has different performance depending on how well the pivot divides the array.
Best Case
If every pivot approximately divides the array in half:
n
↓
n/2 + n/2
↓
n/4 + n/4 + …
Enter fullscreen mode
Exit fullscreen mode
There are approximately:
log n
Enter fullscreen mode
Exit fullscreen mode
levels.
Each level processes approximately:
n
Enter fullscreen mode
Exit fullscreen mode
elements.
Therefore:
O(n log n)
Enter fullscreen mode
Exit fullscreen mode
Average Case
With reasonably good pivot selection, Quick Sort has an average complexity of:
O(n log n)
Enter fullscreen mode
Exit fullscreen mode
Worst Case
Suppose the array is already sorted:
[1, 2, 3, 4, 5, 6, 7]
Enter fullscreen mode
Exit fullscreen mode
and we always choose the last element as the pivot.
Then:
pivot = 7
Enter fullscreen mode
Exit fullscreen mode
gives:
[1, 2, 3, 4, 5, 6] 7
Enter fullscreen mode
Exit fullscreen mode
Next:
pivot = 6
Enter fullscreen mode
Exit fullscreen mode
gives:
[1, 2, 3, 4, 5] 6
Enter fullscreen mode
Exit fullscreen mode
And so on.
Instead of dividing the problem in half, we get:
n
n – 1
n – 2
n – 3
…
Enter fullscreen mode
Exit fullscreen mode
This results in:
O(n²)
Enter fullscreen mode
Exit fullscreen mode
Therefore:
Case
Time Complexity
Best
O(n log n)
Average
O(n log n)
Worst
O(n²)
Space Complexity
Quick Sort is often described as an in-place sorting algorithm because it can partition the array without creating another array proportional to n.
However, recursion requires stack space.
With reasonably balanced partitions:
O(log n)
Enter fullscreen mode
Exit fullscreen mode
stack space is typical.
In the worst case, recursion can become:
O(n)
Enter fullscreen mode
Exit fullscreen mode
deep.
So:
Case
Auxiliary Space
Average
O(log n)
Worst
O(n)
Implementation details and pivot strategy can affect these values.
Common Mistakes
Mistake 1: Confusing partitioning with sorting
Partitioning does not completely sort the array.
For example:
[3, 1, 4, 2] 5 [8, 7]
Enter fullscreen mode
Exit fullscreen mode
The left side isn’t necessarily sorted:
3, 1, 4, 2
Enter fullscreen mode
Exit fullscreen mode
It only satisfies the partition property.
We still need to recursively sort both sides.
Mistake 2: Forgetting the base case
Quick Sort must stop when the partition contains zero or one element.
if (low high) {
// partition and recurse
}
Enter fullscreen mode
Exit fullscreen mode
Without this condition, recursion will not terminate correctly.
Mistake 3: Creating bad partitions repeatedly
Consider:
[1, 2, 3, 4, 5, 6, 7]
Enter fullscreen mode
Exit fullscreen mode
If the pivot is always the largest element:
[1, 2, 3, 4, 5, 6] 7
Enter fullscreen mode
Exit fullscreen mode
we get highly unbalanced partitions.
Repeatedly doing this results in:
O(n²)
Enter fullscreen mode
Exit fullscreen mode
worst-case performance.
Pivot selection matters.
Mistake 4: Assuming Quick Sort is always O(n log n)
Quick Sort is:
Average → O(n log n)
Enter fullscreen mode
Exit fullscreen mode
but:
Worst case → O(n²)
Enter fullscreen mode
Exit fullscreen mode
The quality of the partitions determines the performance.
Mistake 5: Forgetting that duplicates matter
Consider:
[5, 5, 5, 5, 5]
Enter fullscreen mode
Exit fullscreen mode
Depending on the partition scheme, many equal values can lead to poor partitioning.
More sophisticated partition strategies, such as three-way partitioning, can handle many duplicates more efficiently.
Advanced Notes
1. Pivot Selection
The pivot is one of the most important decisions in Quick Sort.
Common approaches include:
First element
pivot = arr[low]
Enter fullscreen mode
Exit fullscreen mode
Simple, but potentially bad for sorted data.
Last element
pivot = arr[high]
Enter fullscreen mode
Exit fullscreen mode
Also simple, but has the same worst-case issue.
Middle element
Choosing a middle position can reduce some bad cases, although it does not guarantee good partitions.
Random pivot
Choose a random element.
Randomization makes consistently bad partition patterns much less likely.
Median-of-three
Choose the median among:
first
middle
last
Enter fullscreen mode
Exit fullscreen mode
This can provide better pivot choices for certain input patterns.
2. Lomuto vs Hoare Partition
The implementation above uses Lomuto partitioning.
Another common approach is Hoare partitioning.
Lomuto is generally easier to understand.
Hoare partitioning can perform fewer swaps and is often more efficient in practice.
Understanding both is useful when implementing Quick Sort from scratch.
3. Three-Way Partitioning
Suppose:
[4, 2, 4, 4, 7, 4, 1]
Enter fullscreen mode
Exit fullscreen mode
There are many duplicates.
Instead of dividing into only two sections:
Enter fullscreen mode
Exit fullscreen mode
we can create three:
pivot
Enter fullscreen mode
Exit fullscreen mode
For pivot 4:
[2, 1] | [4, 4, 4, 4] | [7]
Enter fullscreen mode
Exit fullscreen mode
The equal section requires no further sorting.
This can make Quick Sort much more efficient when there are many duplicate values.
4. Quick Sort vs Merge Sort
Both are fundamental O(n log n) sorting algorithms on average.
Feature
Quick Sort
Merge Sort
Average Time
O(n log n)
O(n log n)
Worst Time
O(n²)
O(n log n)
Typical Auxiliary Space
O(log n)
O(n)
Stable
Usually No
Yes
In-place
Usually Yes
Usually No
Main Operation
Partition
Merge
The biggest conceptual difference is:
Merge Sort:
Divide → Sort → Merge
Quick Sort:
Partition → Sort left/right
Enter fullscreen mode
Exit fullscreen mode
Merge Sort does most of its important work while merging.
Quick Sort does most of its important work while partitioning.
5. Why Quick Sort Can Be Fast in Practice
Even though Merge Sort has a guaranteed O(n log n) worst-case complexity, Quick Sort can be extremely fast in practice.
One reason is that good implementations can operate largely within the original array.
That can provide:
- Good cache behavior
- Low memory overhead
- Fewer allocations
- Efficient in-place partitioning
So algorithm analysis tells us the theoretical behavior, while implementation details influence real-world performance.
6. Tail Recursion Optimization
A careful Quick Sort implementation can reduce recursion depth by recursively processing the smaller partition first and handling the larger partition iteratively.
This can help limit stack usage even when partitions are unbalanced.
This is an example of an important engineering principle:
Algorithm design and implementation strategy both matter.
The Bigger Picture
Quick Sort connects several concepts we’ve already learned.
Big-O
From the previous article:
O(n)
O(log n)
O(n log n)
O(n²)
Enter fullscreen mode
Exit fullscreen mode
Quick Sort demonstrates why average-case and worst-case analysis matter.
Its typical performance is:
O(n log n)
Enter fullscreen mode
Exit fullscreen mode
but poor pivot choices can produce:
O(n²)
Enter fullscreen mode
Exit fullscreen mode
Binary Search
Binary Search taught us the power of reducing a problem by eliminating part of the search space.
Quick Sort uses a related strategy.
Instead of searching:
“Which element am I looking for?”
Enter fullscreen mode
Exit fullscreen mode
we ask:
“Which elements belong on each side of the pivot?”
Enter fullscreen mode
Exit fullscreen mode
Merge Sort
Merge Sort and Quick Sort both use:
Divide and Conquer
Enter fullscreen mode
Exit fullscreen mode
but divide the problem differently.
Merge Sort:
Split by position
↓
Sort
↓
Merge
Quick Sort:
Choose pivot
↓
Partition by value
↓
Sort partitions
Enter fullscreen mode
Exit fullscreen mode
This distinction is extremely important.
Recursion
Quick Sort is another excellent example of recursion.
quickSort(left)
quickSort(right)
Enter fullscreen mode
Exit fullscreen mode
Each call works on a smaller part of the original problem.
The Most Important Mental Model
Don’t think:
“Quick Sort chooses a random element and sorts around it.”
Think:
“Put one pivot into its final position, then solve the two remaining problems.”
For example:
Before:
[8 3 1 7 0 10 2]
Choose pivot = 7
↓
[3 1 0 2] 7 [8 10]
↓
Sort left Sort right
↓
[0 1 2 3] 7 [8 10]
↓
[0 1 2 3 7 8 10]
Enter fullscreen mode
Exit fullscreen mode
The pivot creates a boundary:
everything smaller | pivot | everything larger
Enter fullscreen mode
Exit fullscreen mode
Once that boundary is correct, the original problem becomes two smaller problems.
That’s the essence of Quick Sort.
Summary
Quick Sort is a Divide and Conquer sorting algorithm based on partitioning around a pivot.
The process is:
Choose Pivot
↓
Partition
↓
Pivot reaches final position
↓
Recursively sort left
↓
Recursively sort right
Enter fullscreen mode
Exit fullscreen mode
Important points:
- Quick Sort works by partitioning around a pivot.
- The pivot ends up in its final position after partitioning.
- The remaining partitions are sorted recursively.
- Average time complexity is O(n log n).
- Worst-case time complexity is O(n²).
- Good pivot selection helps avoid poor partitions.
- Quick Sort usually requires less auxiliary memory than Merge Sort.
- Standard Quick Sort is generally not stable.
- Three-way partitioning is useful when many duplicate values exist.
- Quick Sort is one of the most important examples of Divide and Conquer.
The central comparison is:
Merge Sort
↓
Divide → Sort → Merge
Quick Sort
↓
Partition → Sort → Repeat
Enter fullscreen mode
Exit fullscreen mode