Quicksort Algorithm Explained
Quicksort is one of the most important and widely studied sorting algorithms in computer science. It is a divide-and-conquer algorithm that sorts an array by selecting a pivot element, placing smaller values before the pivot, placing larger values after it, and then recursively sorting the remaining parts.
Quicksort is popular because it is usually very fast in practice. Although its worst-case time complexity is O(n²), its average-case performance is O(n log n), which makes it much more efficient than simple algorithms such as Bubble Sort, Selection Sort, and Insertion Sort for large datasets.
Introduction
Sorting algorithms help developers organize data in a meaningful order. Applications use sorting to arrange prices, names, scores, timestamps, search results, database records, analytics output, and many other types of information.
Simple sorting algorithms are useful for learning, but they become slow when the input size grows. Algorithms such as Bubble Sort, Selection Sort, and Insertion Sort usually have O(n²) time complexity, which means their running time grows quickly for large arrays.
Quicksort introduces a more powerful idea. Instead of repeatedly scanning the whole array in a simple way, it divides the problem into smaller subproblems. This divide-and-conquer strategy makes Quicksort one of the most important algorithms for understanding efficient sorting.
What Is Quicksort?
Quicksort is a comparison-based sorting algorithm that works by choosing a pivot element and rearranging the array so that values smaller than the pivot go to one side, and values greater than the pivot go to the other side.
After the partition step, the pivot is in its correct sorted position. Then Quicksort recursively applies the same logic to the left and right parts of the array.
The main idea can be summarized like this:
Choose a pivot element.
Move smaller elements to the left side of the pivot.
Move larger elements to the right side of the pivot.
Recursively sort the left part.
Recursively sort the right part.
Combine the result naturally because the pivot is already in the correct position.
Quicksort is called “quick” because it is usually very fast compared to many basic sorting algorithms.
The Main Idea Behind Quicksort
The most important concept in Quicksort is partitioning. Partitioning means reorganizing the array around a selected pivot.
For example, consider this array:
[8, 3, 1, 7, 0, 10, 2]If we choose 7 as the pivot, the goal is to place all values smaller than 7 before it and all values greater than 7 after it.
Smaller than pivot: [3, 1, 0, 2]
Pivot: [7]
Greater than pivot: [8, 10]After partitioning, the pivot is in the correct general position. The values on the left are not necessarily sorted yet, and the values on the right are not necessarily sorted yet. Quicksort solves that by recursively applying the same process to each side.
Divide and Conquer in Quicksort
Quicksort follows the divide-and-conquer technique. This technique breaks a large problem into smaller problems, solves the smaller problems, and combines the results.
In Quicksort, the process works as follows:
Divide: Choose a pivot and partition the array into smaller and larger elements.
Conquer: Recursively sort the left and right partitions.
Combine: The result is sorted because the left part, pivot, and right part are already in correct order.
This structure is what allows Quicksort to achieve O(n log n) average-case performance.
How Quicksort Works Step by Step
Quicksort can be understood through these steps:
Select a pivot element from the array.
Partition the array so that smaller elements go before the pivot and larger elements go after it.
Apply Quicksort recursively to the left partition.
Apply Quicksort recursively to the right partition.
Stop when a partition has zero or one element because it is already sorted.
The base case is important in recursion. Without a base case, the function would continue calling itself forever.
Manual Run Example
Let us manually sort the following array using Quicksort:
[8, 3, 1, 7, 0, 10, 2]For this manual run, we will use the last element as the pivot.
First Partition
The array is:
[8, 3, 1, 7, 0, 10, 2]The pivot is the last element:
Pivot = 2Now we compare each element with the pivot and move values smaller than or equal to 2 toward the left side.
Using the Lomuto partition idea, the array becomes:
[1, 0, 2, 7, 8, 10, 3]The pivot 2 is now in its correct position. The left side contains values smaller than 2, and the right side contains values greater than 2.
Left part: [1, 0]
Pivot: [2]
Right part: [7, 8, 10, 3]Sorting the Left Part
The left part is:
[1, 0]The pivot is:
Pivot = 0No element is smaller than 0. The value 1 is greater than 0. After partitioning:
[0, 1]The left part is now sorted.
Sorting the Right Part
The right part is:
[7, 8, 10, 3]The pivot is:
Pivot = 3No element is smaller than 3. The values 7, 8, and 10 are greater than 3. After partitioning:
[3, 8, 10, 7]Now 3 is in its correct position inside this partition.
The remaining right part is:
[8, 10, 7]The pivot is:
Pivot = 7No element is smaller than 7. The values 8 and 10 are greater than 7. After partitioning:
[7, 10, 8]The remaining right part is:
[10, 8]The pivot is:
Pivot = 8No element is smaller than 8. The value 10 is greater than 8. After partitioning:
[8, 10]Final Sorted Array
After all recursive calls finish, the final sorted array is:
[0, 1, 2, 3, 7, 8, 10]This manual run shows the main behavior of Quicksort. The algorithm does not build the sorted array one element at a time like Insertion Sort. Instead, it repeatedly partitions the array around pivots until all values are in the correct order.
Quicksort Recursion Tree
Quicksort can be visualized as a recursion tree. Each pivot divides the array into smaller parts.
[8, 3, 1, 7, 0, 10, 2]
pivot 2
/ \
[1, 0] [7, 8, 10, 3]
pivot 0 pivot 3
\ \
[1] [8, 10, 7]
pivot 7
\
[10, 8]
pivot 8
\
[10]When partitions are balanced, the recursion tree is shallow and efficient. When partitions are highly unbalanced, the recursion tree becomes deep and Quicksort becomes slower.
Pseudocode
A simple Quicksort algorithm can be described like this:
quickSort(array, low, high):
if low < high:
pivotIndex = partition(array, low, high)
quickSort(array, low, pivotIndex - 1)
quickSort(array, pivotIndex + 1, high)The partition function places the pivot in its correct position and returns the index of that pivot.
partition(array, low, high):
pivot = array[high]
i = low - 1
for j from low to high - 1:
if array[j] <= pivot:
i = i + 1
swap array[i] with array[j]
swap array[i + 1] with array[high]
return i + 1This version uses the Lomuto partition scheme, where the last element is selected as the pivot.
Quicksort Example in PHP
Here is a clean PHP implementation of Quicksort using the Lomuto partition scheme:
<?php
function quickSort(array &$numbers, int $low, int $high): void
{
if ($low < $high) {
$pivotIndex = partition($numbers, $low, $high);
quickSort($numbers, $low, $pivotIndex - 1);
quickSort($numbers, $pivotIndex + 1, $high);
}
}
function partition(array &$numbers, int $low, int $high): int
{
$pivot = $numbers[$high];
$i = $low - 1;
for ($j = $low; $j < $high; $j++) {
if ($numbers[$j] <= $pivot) {
$i++;
[$numbers[$i], $numbers[$j]] = [$numbers[$j], $numbers[$i]];
}
}
[$numbers[$i + 1], $numbers[$high]] = [$numbers[$high], $numbers[$i + 1]];
return $i + 1;
}
$numbers = [8, 3, 1, 7, 0, 10, 2];
quickSort($numbers, 0, count($numbers) - 1);
print_r($numbers);The output will be:
Array
(
[0] => 0
[1] => 1
[2] => 2
[3] => 3
[4] => 7
[5] => 8
[6] => 10
)This implementation sorts the array in place. The array is passed by reference, so the function modifies the original array instead of creating a completely new one.
Quicksort Example in JavaScript
Here is the same algorithm implemented in JavaScript:
function quickSort(numbers, low = 0, high = numbers.length - 1) {
if (low < high) {
const pivotIndex = partition(numbers, low, high);
quickSort(numbers, low, pivotIndex - 1);
quickSort(numbers, pivotIndex + 1, high);
}
return numbers;
}
function partition(numbers, low, high) {
const pivot = numbers[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (numbers[j] <= pivot) {
i++;
[numbers[i], numbers[j]] = [numbers[j], numbers[i]];
}
}
[numbers[i + 1], numbers[high]] = [numbers[high], numbers[i + 1]];
return i + 1;
}
const numbers = [8, 3, 1, 7, 0, 10, 2];
console.log(quickSort(numbers));The output will be:
[0, 1, 2, 3, 7, 8, 10]The JavaScript version follows the same structure as the PHP version. It chooses the last element as the pivot, partitions the array, and recursively sorts both sides.
Functional Quicksort Example
Quicksort can also be written in a more functional style. This version is easier to read, but it uses extra arrays and therefore needs more memory.
function quickSortFunctional(numbers) {
if (numbers.length <= 1) {
return numbers;
}
const pivot = numbers[numbers.length - 1];
const left = [];
const right = [];
for (let i = 0; i < numbers.length - 1; i++) {
if (numbers[i] <= pivot) {
left.push(numbers[i]);
} else {
right.push(numbers[i]);
}
}
return [
...quickSortFunctional(left),
pivot,
...quickSortFunctional(right)
];
}
console.log(quickSortFunctional([8, 3, 1, 7, 0, 10, 2]));This implementation is useful for learning because it clearly shows the idea of left part, pivot, and right part. However, the in-place version is usually more memory-efficient.
Pivot Selection in Quicksort
The pivot is a critical part of Quicksort. The quality of the pivot affects how balanced the partitions are.
Common pivot selection strategies include:
First element: Simple, but risky if the array is already sorted.
Last element: Simple and common in examples, but can also be risky.
Random element: Reduces the chance of consistently bad partitions.
Middle element: Often better than always choosing the first or last element.
Median-of-three: Chooses the median value among the first, middle, and last elements.
A good pivot divides the array into two reasonably balanced parts. A bad pivot creates one very small partition and one very large partition, which makes the algorithm slower.
Time Complexity of Quicksort
Time complexity describes how the running time of an algorithm grows as the input size increases. For Quicksort, the time complexity depends on how balanced the partitions are after each pivot selection.
Quicksort has three important time complexity cases:
Best case: O(n log n)
Average case: O(n log n)
Worst case: O(n²)
The partition step scans the array once, which costs O(n). The recursive structure determines how many levels of partitioning are needed.
Best Case Time Complexity: O(n log n)
The best case happens when the pivot divides the array into two nearly equal parts each time.
For example, if the pivot splits the array like this:
n elements
n/2 elements + n/2 elements
n/4 elements + n/4 elements + n/4 elements + n/4 elementsThe number of recursion levels becomes approximately log n. At each level, partitioning all elements together costs O(n).
Therefore, the best case time complexity is:
O(n log n)This is the ideal behavior of Quicksort.
Average Case Time Complexity: O(n log n)
The average case happens when pivots are not perfect but still divide the array into reasonably balanced parts most of the time.
In real applications, this is the common behavior of Quicksort, especially when the pivot is chosen carefully or randomly.
The average case time complexity is:
O(n log n)This is why Quicksort is considered very efficient in practice.
Worst Case Time Complexity: O(n²)
The worst case happens when the pivot repeatedly creates highly unbalanced partitions.
For example, if the array is already sorted and the algorithm always chooses the last element as the pivot:
[1, 2, 3, 4, 5]The pivot is always the largest element. This means one partition contains almost all elements and the other partition is empty.
The recursive breakdown becomes:
n
n - 1
n - 2
n - 3
...
1The total work becomes approximately:
n + (n - 1) + (n - 2) + ... + 1This grows as n², so the worst case time complexity is:
O(n²)This is why pivot selection matters so much in Quicksort.
Space Complexity of Quicksort
Space complexity describes how much extra memory an algorithm uses. In-place Quicksort does not need an additional array for sorting, but it does use memory for recursive function calls.
The average space complexity is:
O(log n)This happens when partitions are balanced and the recursion depth is around log n.
The worst-case space complexity is:
O(n)This happens when partitions are extremely unbalanced and the recursion depth becomes n.
If Quicksort is implemented using extra left and right arrays, the space complexity becomes higher because new arrays are created during recursion.
Is Quicksort Stable?
Quicksort is usually not stable in its common in-place implementations.
A stable sorting algorithm preserves the relative order of equal elements. For example, if two products have the same price, a stable sort keeps them in the same order they appeared before sorting.
Quicksort may swap equal elements during partitioning, which can change their original order. Because of this, standard in-place Quicksort is considered unstable.
It is possible to create a stable version of Quicksort, but it usually requires extra memory or a modified partitioning approach.
Is Quicksort In-Place?
Quicksort can be implemented as an in-place sorting algorithm. The common partition-based implementation rearranges elements inside the original array using swaps.
However, not every Quicksort implementation is in-place. The functional version that creates separate left and right arrays is easier to read, but it uses extra memory.
So the correct answer is:
In-place Quicksort: yes, when implemented with partitioning and swaps.
Functional Quicksort: no, because it creates additional arrays.
Quicksort vs Merge Sort
Quicksort and Merge Sort are both efficient divide-and-conquer sorting algorithms. Both usually perform much better than simple O(n²) algorithms on large datasets.
However, they have different characteristics.
Quicksort has average time complexity O(n log n).
Merge Sort has guaranteed time complexity O(n log n).
Quicksort can sort in place with low extra memory.
Merge Sort usually needs additional memory for merging.
Quicksort is usually not stable.
Merge Sort is stable when implemented correctly.
Quicksort is often faster in practice for arrays because it has good cache performance and low memory overhead. Merge Sort is often preferred when stability is required or when sorting linked lists.
Quicksort vs Insertion Sort
Insertion Sort is simple and efficient for small or nearly sorted arrays. Quicksort is more efficient for larger random datasets.
Many real sorting implementations use a hybrid approach. They use Quicksort or a similar divide-and-conquer algorithm for large partitions, then switch to Insertion Sort when partitions become small.
This works well because Insertion Sort has low overhead on small arrays, while Quicksort handles large-scale division efficiently.
When Should Developers Use Quicksort?
Developers should consider Quicksort when they need an efficient general-purpose sorting algorithm and stability is not required.
Quicksort is useful when:
The dataset is medium or large.
Average-case performance is important.
Extra memory usage should be low.
The data is stored in an array.
A fast in-place sorting algorithm is needed.
The implementation can use a good pivot strategy.
In most production applications, developers should use the built-in sorting functions of their programming language. These functions are usually optimized and tested for many edge cases.
When Not to Use Quicksort
Quicksort may not be the best choice in every situation.
Developers should avoid basic Quicksort when:
Stable sorting is required.
The input may often be already sorted and pivot selection is weak.
Worst-case O(n²) behavior is unacceptable.
Recursion depth may become a problem.
The programming environment has limited stack memory.
In such cases, Merge Sort, Heap Sort, TimSort, or built-in sorting functions may be better choices.
Common Mistakes When Implementing Quicksort
Quicksort is more complex than Bubble Sort, Selection Sort, and Insertion Sort, so beginners often make mistakes in the partition logic or recursive boundaries.
Common mistakes include:
Forgetting the base case of recursion.
Using wrong low and high indexes.
Returning the wrong pivot index from partition.
Including the pivot again in recursive calls.
Always choosing a bad pivot.
Mixing different partition schemes incorrectly.
Using extra arrays without understanding the memory cost.
The most important implementation detail is to ensure that the partition function correctly places the pivot and returns its final index.
Practical Example: Sorting Product Prices
Imagine an e-commerce system that needs to sort product prices from lowest to highest. Quicksort can be used to sort the price list efficiently.
<?php
$prices = [99.99, 29.99, 49.99, 19.99, 79.99];
quickSort($prices, 0, count($prices) - 1);
print_r($prices);The result will be:
Array
(
[0] => 19.99
[1] => 29.99
[2] => 49.99
[3] => 79.99
[4] => 99.99
)This example is simple, but it shows how Quicksort can be connected to real data that developers handle in applications.
Practical Checklist for Understanding Quicksort
Before moving to more advanced sorting topics, developers should be able to answer these questions:
What is the role of the pivot?
What does partitioning mean?
Why does Quicksort use recursion?
What is the base case of Quicksort?
Why is the average time complexity O(n log n)?
Why can the worst case become O(n²)?
How does pivot selection affect performance?
Is Quicksort stable?
Is Quicksort in-place?
If these questions are clear, the developer understands the real logic of Quicksort instead of only memorizing the code.
Advantages of Quicksort
Quicksort has several advantages that make it one of the most famous sorting algorithms.
It is fast in average cases.
It has O(n log n) average time complexity.
It can be implemented in place.
It usually uses less extra memory than Merge Sort.
It works well for arrays.
It teaches important concepts such as recursion, partitioning, and divide-and-conquer.
These advantages make Quicksort an essential algorithm for students and developers.
Disadvantages of Quicksort
Quicksort also has limitations that developers should understand.
Its worst-case time complexity is O(n²).
It is usually not stable.
Bad pivot selection can reduce performance.
Recursive calls may use stack memory.
The partition logic can be harder to implement correctly than simple sorting algorithms.
Because of these limitations, production systems often use optimized or hybrid sorting algorithms instead of a simple textbook Quicksort.
Conclusion
Quicksort is a powerful divide-and-conquer sorting algorithm that sorts data by selecting a pivot, partitioning the array around that pivot, and recursively sorting the smaller parts.
Its average and best case time complexity is O(n log n), which makes it much faster than Bubble Sort, Selection Sort, and Insertion Sort for large random datasets. However, its worst-case time complexity is O(n²), especially when pivot selection creates highly unbalanced partitions.
Quicksort can be implemented in place, which makes it memory-efficient compared to sorting algorithms that require additional arrays. However, it is usually not stable, and its recursive nature requires careful implementation.
For developers learning algorithms, Quicksort is an important step because it teaches recursion, partitioning, pivot selection, and divide-and-conquer thinking. Understanding Quicksort prepares developers to study more advanced algorithms and to better understand how efficient sorting works in real software systems.
