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
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]
We want:
[0, 1, 2, 3, 7, 8, 10]
One approach is Merge Sort:
Divide → Sort → Merge
Quick Sort takes another approach:
Choose pivot
↓
Partition
↓
Sort left side
↓
Sort right side
For example, choose:
pivot = 7
Rearrange the array around it:
[3, 1, 0, 2] 7 [8, 10]
Now 7 is in its correct final position.
We only need to sort:
[3, 1, 0, 2]
and:
[8, 10]
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
Step 1: Choose a pivot
The pivot can be selected in several ways:
First element
Last element
Middle element
Random element
Median-based strategy
For a simple implementation, we can choose the last element.
Step 2: Partition
Rearrange the array so that:
values < pivot
↓
pivot
↓
values > pivot
For example:
[6, 3, 8, 5, 2, 7, 4]
↑
pivot
After partitioning:
[3, 5, 2, 4] [6] [8, 7]
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]
and:
[8, 7]
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
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
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
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);
}
}
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;
}
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 + " ");
}
}
Output:
0 1 2 3 7 8 10
Understanding Partition
This is the most important part of Quick Sort.
Consider:
[4, 2, 7, 3, 1, 6]
Suppose:
pivot = 6
We want:
[values ≤ 6] 6 [values > 6]
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]
The pivot is now correctly positioned.
We then recursively sort:
[4, 2, 3, 1]
and:
[7]
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]
Choose:
pivot = 5
After partitioning:
[4, 2, 1, 3] 5 [8, 7]
Everything on the left belongs before 5.
Everything on the right belongs after 5.
Therefore, the original problem:
Sort 7 elements
becomes:
Sort 4 elements
+
Sort 2 elements
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 + ...
There are approximately:
log n
levels.
Each level processes approximately:
n
elements.
Therefore:
O(n log n)
Average Case
With reasonably good pivot selection, Quick Sort has an average complexity of:
O(n log n)
Worst Case
Suppose the array is already sorted:
[1, 2, 3, 4, 5, 6, 7]
and we always choose the last element as the pivot.
Then:
pivot = 7
gives:
[1, 2, 3, 4, 5, 6] 7
Next:
pivot = 6
gives:
[1, 2, 3, 4, 5] 6
And so on.
Instead of dividing the problem in half, we get:
n
n - 1
n - 2
n - 3
...
This results in:
O(n²)
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)
stack space is typical.
In the worst case, recursion can become:
O(n)
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]
The left side isn't necessarily sorted:
3, 1, 4, 2
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
}
Without this condition, recursion will not terminate correctly.
Mistake 3: Creating bad partitions repeatedly
Consider:
[1, 2, 3, 4, 5, 6, 7]
If the pivot is always the largest element:
[1, 2, 3, 4, 5, 6] 7
we get highly unbalanced partitions.
Repeatedly doing this results in:
O(n²)
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)
but:
Worst case → O(n²)
The quality of the partitions determines the performance.
Mistake 5: Forgetting that duplicates matter
Consider:
[5, 5, 5, 5, 5]
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]
Simple, but potentially bad for sorted data.
Last element
pivot = arr[high]
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
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]
There are many duplicates.
Instead of dividing into only two sections:
< pivot | ≥ pivot
we can create three:
< pivot | = pivot | > pivot
For pivot 4:
[2, 1] | [4, 4, 4, 4] | [7]
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
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²)
Quick Sort demonstrates why average-case and worst-case analysis matter.
Its typical performance is:
O(n log n)
but poor pivot choices can produce:
O(n²)
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?"
we ask:
"Which elements belong on each side of the pivot?"
Merge Sort
Merge Sort and Quick Sort both use:
Divide and Conquer
but divide the problem differently.
Merge Sort:
Split by position
↓
Sort
↓
Merge
Quick Sort:
Choose pivot
↓
Partition by value
↓
Sort partitions
This distinction is extremely important.
Recursion
Quick Sort is another excellent example of recursion.
quickSort(left)
quickSort(right)
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]
The pivot creates a boundary:
everything smaller | pivot | everything larger
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
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
Top comments (0)