Quicksort is one of the most widely used sorting algorithms in computer science. First developed by Tony Hoare in 1959, it has stood the test of time because of its efficiency and elegance. At its heart, Quicksort follows a divide-and-conquer strategy: the data is repeatedly split into smaller sections, which are then sorted individually until the whole list is ordered.
How Quicksort Works
The algorithm begins by selecting a pivot element from the list. All values smaller than the pivot are moved to one side, while values greater than the pivot are moved to the other. Once this partitioning is complete, the pivot is in its final position. The process is then repeated on the left and right sections of the list until the entire collection is sorted. Because each pivot is guaranteed to end up in its correct place, no extra merging is required. See this visualisation.
Complexity and Performance
On average, Quicksort achieves excellent performance with a time complexity of O(n log n). This is because each partition tends to divide the list into roughly equal halves. However, if the pivot choices are poor, such as always choosing the first element in an already sorted list, the algorithm can degrade to O(n²). To counteract this, many implementations use strategies such as random pivot selection or choosing the median of three elements. In terms of memory, Quicksort is efficient because it usually works in place, requiring only a small amount of additional space for recursion.
Implementation Choices
There are several variations of Quicksort, particularly in how the partitioning is handled. Two of the most common approaches are the Lomuto and Hoare partition schemes. The Lomuto scheme is straightforward to implement, while Hoare’s original version often requires fewer swaps. Other refinements include handling duplicate values with a three-way partition and switching to insertion sort for very small sections, which reduces overhead and speeds up practical performance.
Teaching and Visualising Quicksort
Because the algorithm can feel abstract when described in words alone, interactive resources and visual demonstrations are especially valuable. The Ada Computer Science platform provides an interactive Quicksort visualiser, while the Hong Kong University COMP152 slides present a clear academic explanation.
A good video overview can be found here:
You can also see a Hungarian Dance video of the Quick Sort
Implementations
Below are two simple implementations of Quicksort: one in Python, and one in Java. They use the Lomuto partition for clarity, and are not fully optimised; but they illustrate the main ideas.
Python
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)
return arr
def partition(arr, lo, hi):
# Lomuto partition: pivot is arr[hi]
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
return i
# Example usage:
data = [3, 7, 2, 5, 1, 4, 6]
print(quicksort(data)) # prints a sorted listJava
public class QuickSort {
public static void quicksort(int[] arr, int lo, int hi) {
if (lo < hi) {
int p = partition(arr, lo, hi);
quicksort(arr, lo, p - 1);
quicksort(arr, p + 1, hi);
}
}
private static int partition(int[] arr, int lo, int hi) {
int pivot = arr[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
if (arr[j] <= pivot) {
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
// swap arr[i] and arr[hi]
int temp = arr[i];
arr[i] = arr[hi];
arr[hi] = temp;
return i;
}
public static void main(String[] args) {
int[] data = {3, 7, 2, 5, 1, 4, 6};
quicksort(data, 0, data.length - 1);
for (int x : data) {
System.out.print(x + " ");
}
System.out.println();
}
}
For IB Quick Sort there is more information in the book: IB DP Computer Science
