Quicksort

IB Syllabus: B2.4.4 (HL) – Explain the fundamental concept of recursion and its applications in programming. Quicksort is listed as a recursive algorithm application; O(n log n) average-case, O(n^2) worst case.

This page is HL only.

Key Concepts
Worked Examples
Quick Code Check
Trace Exercise
1. Trace 1: Partition an 8-element array
2. Trace 2: Partition a 6-element array
Fill in the Prose
Spot the Claim
Predict the Output
Reference: Quicksort in Java
Practice Exercises
Optional Exploration
Connections

Key Concepts

What Quicksort Does

Quicksort sorts an array by repeatedly splitting it around a chosen element called the pivot. Each split places the pivot in its correct final position with smaller values on its left and larger values on its right. The two sides are then sorted by the same process, until every sub-array has 0 or 1 elements and is already sorted.

The steps in plain English:

If the sub-array has 0 or 1 elements, stop – it is already sorted. (base case)
Pick a pivot element (for example, the last element of the sub-array).
Partition: scan the other elements and move those smaller than or equal to the pivot to the left, and those larger than the pivot to the right.
Place the pivot between the two groups. It is now in its final sorted position.
Apply the same process to the left sub-array and to the right sub-array.
When every recursive call has reached a sub-array of 0 or 1 elements, the whole array is sorted.

The Key Insight

After each partition, the pivot is in its final position – it will never move again. That is why quicksort has no combine step: the sort happens during partitioning, not after. The recursive calls only need to fix the two sides; the pivot is already where it belongs.

Complexity

Case	Complexity	What it looks like
Best	O(n log n)	Pivot splits the sub-array roughly in half every time
Average	O(n log n)	Random input – partitions are roughly balanced
Worst	O(n^2)	Pivot is always the smallest or largest element (for example, last-element pivot on a sorted array)

Every partition scans O(n) elements. If the pivot produces balanced splits, the recursion is log n levels deep, giving O(n) x O(log n) = O(n log n). If every split is one-sided, the recursion is n levels deep, giving O(n) x O(n) = O(n^2).

Memory

Quicksort rearranges values within the original array – it does not need an extra array the size of the input. It only uses memory for the call stack, which grows with the depth of the recursion (O(log n) on average, O(n) in the worst case).

Equal Values

Elements equal to the pivot move to the left side in the partition shown on this page. Quicksort is not guaranteed to preserve the original left-to-right order of elements with equal values – two “5”s could swap past each other during partitioning.

You Already Know This

Quicksort is the first algorithm on this page that is genuinely new, but the ingredients are not:

Bubble sort and selection sort (Sorting Algorithms) gave you two O(n^2) baselines. Quicksort is the first sort you meet that beats them on average.
Big-O notation (Big-O) is what lets you compare O(n log n) to O(n^2).
Recursion (Recursion, earlier this week) supplies the base case / recursive case split and the call-stack picture that explains why recursion costs memory.
BST structure (Binary Search Trees) gave you the smaller-left / larger-right rule. The partition step uses that same rule on an array instead of a tree.
Array indexing and swaps (1D Arrays) are the mechanics of partitioning.

Note for IB CS learners (B2.4 syllabus): Quicksort sits under B2.4.4 – Explain recursion and its applications. The assessment verb is explain: you describe quicksort in prose, trace a single partition step, explain best / average / worst cases, and answer the syllabus linking question “Can a BST play a role in the quicksort algorithm?”. Quicksort construction is not on the exam – B2.4.3 restricts sorting construction to bubble sort and selection sort, and B2.4.5 restricts recursive construction to simple non-branching recursive algorithms. The Java code on this page is reference material for running the algorithm and adapting it for an IA project, not a construct task.

Worked Examples

Each example is demonstrator material – read through it and make sure every step makes sense. The construct-level exercises for this topic are on other pages (you already wrote bubble sort and selection sort); here the goal is to understand, trace, and describe.

Example 1: One full partition step

Starting array: [7, 2, 1, 6, 8, 5, 3, 4]. Pivot = 4 (the last element).

Two pointers do the work of partition:

i starts at -1. It tracks the right edge of the “smaller or equal to pivot” section.
j scans from left to right through indices 0 to 6 (everything except the pivot).
When arr[j] <= pivot: increment i, then swap arr[i] with arr[j]. This pulls the small value into the left section.
At the end, swap arr[i + 1] with the pivot, placing the pivot between the two sections.

Step	j	arr[j]	arr[j] <= 4?	Action	i	Array state
start	–	–	–	initialise	-1	[7, 2, 1, 6, 8, 5, 3, 4]
1	0	7	No	skip	-1	[7, 2, 1, 6, 8, 5, 3, 4]
2	1	2	Yes	i=0, swap(0, 1)	0	[2, 7, 1, 6, 8, 5, 3, 4]
3	2	1	Yes	i=1, swap(1, 2)	1	[2, 1, 7, 6, 8, 5, 3, 4]
4	3	6	No	skip	1	[2, 1, 7, 6, 8, 5, 3, 4]
5	4	8	No	skip	1	[2, 1, 7, 6, 8, 5, 3, 4]
6	5	5	No	skip	1	[2, 1, 7, 6, 8, 5, 3, 4]
7	6	3	Yes	i=2, swap(2, 6)	2	[2, 1, 3, 6, 8, 5, 7, 4]
final	–	–	–	swap(i+1=3, pivot at 7)	–	[2, 1, 3, 4, 8, 5, 7, 6]

After partition: pivot 4 is at index 3 – its correct sorted position.

Left sub-array: [2, 1, 3] (indices 0-2, all <= 4)
Right sub-array: [8, 5, 7, 6] (indices 4-7, all > 4)

Quicksort now recurses on [2, 1, 3] and on [8, 5, 7, 6].

Example 2: The full recursion tree (reference)

Continuing from Example 1, if each recursive call also uses its last element as pivot, the complete recursion tree looks like this. Each node is labelled with the pivot chosen at that call.

                   4                <- root: first pivot
                 /   \
                3     6             <- left sub-array pivot, right sub-array pivot
               /     / \
              1     5   8
               \         \
                2         7

Reading the tree in order (left subtree, root, right subtree) at every node reproduces the sorted output [1, 2, 3, 4, 5, 6, 7, 8]. Each pivot was already placed in its final position by partitioning, so no further rearrangement is needed after the recursion unwinds.

What this tree is not: a data structure that quicksort builds or stores. It is a picture of the call chain – a drawing of who calls whom. Students sometimes trace this by hand in a classroom walkthrough, but exam questions ask only about a single partition step, not a full recursion tree.

Example 3: Quicksort’s recursion tree IS a BST

Lay the Example 2 tree next to a BST built by inserting the pivots in call order (4, then 3, then 6, then 1, then 5, then 8, then 2, then 7):

   Quicksort recursion tree          BST after inserting 4,3,6,1,5,8,2,7
            4                                     4
          /   \                                 /   \
         3     6                               3     6
        /     / \                             /     / \
       1     5   8                           1     5   8
        \         \                           \         \
         2         7                           2         7

The two trees are identical. They follow the same ordering rule:

BST: each node’s left subtree holds smaller keys, right subtree holds larger keys.
Quicksort partition: each pivot’s left side holds smaller values, right side holds larger values.

Same rule, different container. That is why quicksort’s recursion tree is structurally a BST.

Example 4: Best vs worst case recursion tree

Best case – pivot splits every sub-array into halves of (nearly) equal size.

For n = 7 (say [4, 2, 6, 1, 3, 5, 7] with a kind pivot choice), the tree is roughly balanced:

         pivot
        /     \
     pivot   pivot          <- level 2
     /  \    /  \
   ...  ...  ... ...        <- level 3  (total log2(7) ~ 3 levels)

Total work: O(n) per level x log n levels = O(n log n).

Worst case – pivot is always the smallest (or largest) element.

For the already-sorted input [1, 2, 3, 4, 5] with the last element chosen as pivot, every partition puts everything on one side:

The tree is lopsided: n levels deep instead of log n. Total work: O(n) per level x n levels = O(n^2). This is the same failure mode a BST shows when values are inserted in sorted order – the tree becomes a chain rather than a balanced shape.

Mitigating the worst case (know that these exist; you do not implement them):

Pick the pivot randomly.
Pick the median of three chosen elements (for example, the first, middle, and last) and use that value as the pivot.

Neither approach removes the worst case entirely, but each makes it extremely unlikely on real-world input.

Quick Code Check

Q1. Partition the array [5, 3, 8, 4, 2, 7, 1, 6] with the last element (6) as the pivot. After this one full partition step, what is the pivot's final index?

Q2. Which input produces quicksort's O(n^2) behaviour when the last element is always chosen as the pivot?

Q3. What is quicksort's average-case time complexity?

Q4. After one full partition step with pivot P, what is true about P's position?

Q5. During recursion, quicksort reaches a sub-array of just 1 element. What happens next?

Q6. Which of these algorithms is recursive?

Q7. Why does quicksort fail to achieve O(n log n) on an already-sorted input when the last element is used as the pivot?

Trace Exercise

Every trace on this page is one partition step – a single pass of the partition scan. You are not asked to trace a full recursion tree; that is demonstrator material only.

Trace 1: Partition an 8-element array

Partition [8, 3, 6, 1, 4, 9, 2, 5] with the last element (5) as the pivot. i starts at -1; j scans indices 0 to 6.

Trace: For each row, enter the new value of i and the array state after that step.

Step	j	arr[j]	arr[j] <= 5?	Action	i after	Array after
1	0	8	No	skip		[8, 3, 6, 1, 4, 9, 2, 5]
2	1	3	Yes	i++, swap(i, j)
3	2	6	No	skip		[3, 8, 6, 1, 4, 9, 2, 5]
4	3	1	Yes	i++, swap(i, j)
5	4	4	Yes	i++, swap(i, j)
6	5	9	No	skip		[3, 1, 4, 8, 6, 9, 2, 5]
7	6	2	Yes	i++, swap(i, j)
final	--	--	--	swap(i+1, pivot)	--

Pivot (5) final index:

Trace 2: Partition a 6-element array

Partition [7, 2, 9, 1, 6, 4] with the last element (4) as the pivot. i starts at -1; j scans indices 0 to 4.

Trace: Work through the partition. Enter i after each step and the array state after any swap.

Step	j	arr[j]	arr[j] <= 4?	i after	Array after
1	0	7			[7, 2, 9, 1, 6, 4]
2	1	2
3	2	9			[2, 7, 9, 1, 6, 4]
4	3	1
5	4	6			[2, 1, 9, 7, 6, 4]
final	--	--	swap(i+1, pivot)	--

Pivot (4) final index: . Left sub-array: . Right sub-array:

Fill in the Prose

Quicksort is an explain-only topic, so the usual code-completion exercise is replaced with a prose completion – the same shape as an exam “describe in prose” answer with key words blanked out. Being able to write this cleanly from memory is the most important preparation for an algorithm-description question.

Fill in the blanks: complete the description of how quicksort sorts an array.

Quicksort sorts an array by first choosing an element called the . It then the array so that all values smaller than or equal to that element move to the and all values larger move to the . After this step, the pivot is in its sorted position. Quicksort is then called on each side. The process stops once a sub-array contains or 0 elements -- this is the case.

Accepted synonyms where meaning is preserved (for self-marking): “final” / “correct”; “recursively” / “recursive”; “base” / “terminating”.

Spot the Claim

Quicksort’s “bugs” are conceptual: common statements that sound plausible but are wrong, or plausible-but-right statements that students doubt. For each claim, decide whether it is correct and read the explanation.

Claim 1. "Quicksort always runs in O(n log n) time."

Claim 2. "After the first partition step, the pivot is in its final sorted position."

Claim 3. "Quicksort uses the same amount of memory regardless of the input."

Claim 4. "If we always pick the middle element as the pivot, quicksort can never reach O(n^2)."

Claim 5. "Merge sort always needs more memory than quicksort."

Predict the Output

These exercises give you a completed partition or a completed recursion tree and ask you to read off a specific result. You do not trace the full recursion yourself.

Predict: After one partition step on [9, 3, 7, 1, 5] with pivot 5, the array becomes [3, 1, 5, 9, 7]. What is the left sub-array (the section before the pivot)?

Predict: The recursion tree below shows each pivot chosen when quicksort runs on a 4-element array. What is the final sorted array?

Predict: After one partition step on [5, 3, 8, 4, 2, 7, 1, 6] with pivot 6, where does the pivot end up? Give its index.

Reference: Quicksort in Java

This code is the Java form of the algorithm described above. You are not asked to reproduce it from memory on an exam, and no practice exercise on this page asks you to write it. It is provided so that you can run quicksort yourself – for instance, to compare its speed to bubble sort on large arrays – and so that students whose IA project needs fast sorting can adapt it.

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {                            // base case: 0 or 1 elements
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);     // sort left sub-array
        quickSort(arr, pivotIndex + 1, high);    // sort right sub-array
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];                        // choose last element as pivot
    int i = low - 1;                              // right edge of smaller section
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];                    // swap arr[i] and arr[j]
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];                        // place pivot in correct position
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;                                 // return pivot's final index
}

To sort a whole array, call quickSort(data, 0, data.length - 1) – the initial call covers the full range, and the recursion handles the sub-arrays from there.

Practice Exercises

Every exercise below is an explain / trace / compare question. None asks you to write quicksort from scratch – that is outside the assessed scope for this topic. Mark allocations follow the IB Paper 2 conventions that the current alignment uses; readers outside that context can treat them as a guide to each question’s relative weight.

Core

1. Define the term “pivot” in the context of the quicksort algorithm. [2 marks]

2. State the base case for the recursive quicksort algorithm. [1 mark]

3. Outline the main steps of the quicksort algorithm. [3 marks]

4. Trace one partition step on the array [6, 2, 8, 4, 1, 3] using the last element (3) as the pivot. Show the state of the array after each comparison and the final position of the pivot. [4 marks]

Extension

5. Describe, in prose, how the quicksort algorithm sorts an array. You are not required to write code. [5 marks]

6. Explain why quicksort’s worst-case time complexity is O(n^2) even though its average case is O(n log n). [3 marks]

7. Compare quicksort with bubble sort. Your answer should address time complexity and when each sort is preferred. [4 marks]

8. Explain the structural link between quicksort’s recursion tree and a binary search tree. [3 marks]

Exam-Style (14 marks)

9. A timekeeper at a school athletics meet records finish times for 32 runners and needs the list sorted from fastest to slowest.

(a) State one advantage of using quicksort over bubble sort to produce this sorted list. [2 marks]

(b) State one disadvantage of quicksort compared to bubble sort. [2 marks]

(c) Describe, without writing code, how the quicksort algorithm would begin sorting the timekeeper’s array of finish times. Include the role of the pivot and the partition process, and refer to a concrete step on the data. [4 marks]

(d) The timekeeper’s software already sorts the list after every runner finishes, so the array at the end of the event is almost in order. Explain why quicksort (with the last element as pivot) would perform poorly on this near-sorted input. [2 marks]

(e) Explain the structural link between quicksort’s recursion tree and a binary search tree. [2 marks]

(f) Merge sort needs an extra array the same size as the input in order to sort. Explain why this is a disadvantage compared to quicksort. [2 marks]

Answer sketches

Worked answers with concept-based mark schemes are in the teacher guide. Quick pointers for self-checkers:

Q1: The pivot is the element chosen during each recursive call around which the sub-array is partitioned; after partitioning, it sits in its final sorted position.
Q2: A sub-array of 0 or 1 elements – it is already sorted, so quicksort returns without recursing.
Q4: [6, 2, 8, 4, 1, 3] with pivot 3 – scan gives i = -1, 2 swapped to index 0 (i=0), 1 swapped to index 1 (i=1). Final swap places pivot at index 2. Result: [2, 1, 3, 4, 8, 6]. Pivot 3 at index 2; left [2, 1], right [4, 8, 6].
Q6: Worst case occurs when the pivot is always the smallest or largest element of the sub-array, so every partition is one-sided. The recursion becomes n levels deep instead of log n; O(n) work x n levels = O(n^2).
Q8: Each pivot follows the BST ordering rule – smaller values go left, larger go right – so drawing the recursion tree with pivots as nodes produces exactly the BST that insertion in call order would build. Both share the same worst-case shape on sorted input: a one-sided chain.

Optional Exploration

There is no GitHub Classroom assignment for quicksort. This topic is described, traced, and compared on paper – you are not assessed on writing quicksort code. What you can do optionally is run the reference code above and see for yourself how much faster it is than the sorts you wrote earlier.

Copy the reference quicksort code into BlueJ (or a Codespace) alongside the bubble-sort and selection-sort code from your earlier sorting lesson. Add a helper that generates a random array of a given size.
Time each sort on arrays of size 100, 1,000, and 10,000 using System.nanoTime(). Record the results.
Plot or tabulate the timings. The gap between O(n^2) and O(n log n) should be obvious by n = 10,000.
If your IA project needs to sort data (leaderboards, rankings, transaction ordering, and so on), this reference code is a legitimate building block – adapt it rather than rewriting it.

This exploration is entirely optional and has no tests, no autograding, and no submission.

Connections

Prerequisites: Recursion – base case, recursive case, call stack. Quicksort is the canonical branching-recursion example.
Prerequisites: Sorting Algorithms – bubble sort and selection sort supply the O(n^2) baselines quicksort is compared against.
Prerequisites: Big-O Notation – you need the distinction between O(n log n) and O(n^2) to make sense of best / average / worst.
Prerequisites: Binary Search Trees – partition uses the same smaller-left / larger-right rule. The BST link is a named syllabus linking question.
Prerequisites: 1D Arrays – indices, swaps, and sub-array reasoning power the partition step.
Related: Searching Algorithms – binary search is another O(log n) / divide-and-conquer idea, this time on a sorted array rather than an unsorted one.
Forward: Merge sort – not implemented this year, but mentioned for comparison: guaranteed O(n log n) worst case, at the cost of needing an extra array the same size as the input.