Algorithms · Lecture Notes

Chapter 3: Sorting Algorithms

Sorting is one of the oldest and most thoroughly studied problems in computer science. The problem is simple: arrange the elements of an array from smallest to largest. Yet its solutions display nearly all the basic ideas of algorithm design: brute force, the incremental approach, divide and conquer, random choice, exploiting a data structure, and counting without comparing. These notes begin with the criteria used to evaluate a sorting algorithm. They then cover bubble, insertion, selection, and Shell sort, followed by merge sort, quicksort, and heap sort. Next come the lower bound for comparison sorting and the counting, radix, and bucket sorts that get around it. The last sections treat Timsort and an empirical comparison of the algorithms.

Learning outcomes

Concepts
Evaluate a sorting algorithm by time, extra memory, stability, in-place operation, adaptivity, and whether it is comparison-based.
Simple algorithms
Trace bubble, insertion, selection, and Shell sort step by step on an array, write them in Java, and compute their comparison and move counts.
Divide and conquer, heaps
Explain how merge sort, quicksort, and heap sort work; justify their O(n log n) running times and worst-case behavior.
Linear time and selection
Prove the comparison lower bound; explain why counting, radix, and bucket sort can beat it; and choose a suitable algorithm for a given problem.

3.1The sorting problem and evaluation criteria

To say whether an algorithm is good, we must first define the problem precisely and then decide what "good" is measuring. This section defines the sorting problem, briefly introduces the algorithms of the chapter, and explains the criteria we will use to compare them. One criterion, stability, comes up several times in the chapter and gets a subsection of its own.

3.1.1What is sorting?

Data is everywhere in daily life: shopping lists, bank transactions, social media posts, exam results. To be useful, it usually has to be kept in some order. An inbox is arranged by date, a dictionary by alphabet, a grade list by score. Sorting is the task of putting the items of a list in order according to some criterion. The criterion can be numeric value, alphabetical order, or date, and the order can be ascending (smallest to largest) or descending. Unless stated otherwise, these notes sort integers in ascending order. Descending order only requires reversing the direction of the comparison.

Definition 3.1

Input: a sequence of n numbers ⟨a1, a2, …, an⟩.
Output: a permutation (reordering) ⟨a′1, a′2, …, a′n⟩ of the same numbers that satisfies a′1 ≤ a′2 ≤ … ≤ a′n.

Both conditions in the definition matter. The output must be sorted, but that is not enough: it must also be a permutation of the input. No element may be lost, none duplicated, and no new value introduced. An "algorithm" that sets every element to 0 produces a sorted sequence, but it is not correct, because it violates the permutation condition.

In real applications, what gets sorted is often not a single number but a record: a row holding, say, a student number, a name, and a department. The field of the record used for sorting is called the key. The other fields of the record travel along with the key. In this chapter's examples a record consists of the key alone; for stability we will attach a label to each key.

Unsorted72941sort (ascending)Sorted12479
Figure 3.1: The sorting problem. The unsorted sequence 7, 2, 9, 4, 1 becomes 1, 2, 4, 7, 9 in ascending order. The output is a rearrangement of the five input numbers.

Why is sorting so important? Because many operations become much easier on sorted data. In a sorted array, binary search finds a value in O(log n) steps, whereas in an unsorted array the worst case inspects every element. Duplicates sit next to each other in a sorted array, so finding them takes a single pass. Two sorted lists can be merged in one pass. The median, the minimum, or the largest k elements can be read directly by index. For this reason sorting is often not a goal in itself but the first step of another algorithm.

3.1.2Kinds of algorithms

Many algorithms solve the sorting problem, and each rests on a different working principle. Table 3.1 lists the algorithms studied in this chapter with their central ideas. The first four are simple and quadratic. The next three run in n log n time. Counting sort and radix sort do not compare elements. Timsort is a hybrid of two algorithms and is the one used today for sorting objects in the Java and Python libraries.

Table 3.1: The sorting algorithms of this chapter and their central ideas.
AlgorithmCentral idea
Bubble sortCompares neighbors and swaps them if they are out of order.
Insertion sortInserts the next element into its proper place in the sorted part.
Selection sortFinds the smallest element, puts it first, then sorts the rest the same way.
Shell sortInsertion-sorts distant elements first, with gaps that shrink step by step.
Merge sortSplits the array in half, sorts the halves, then merges them.
QuicksortPartitions around a pivot and sorts the two parts recursively.
Heap sortBuilds a max-heap and repeatedly moves the largest element to the end.
Counting / radix sortNo comparisons; counts the keys or distributes them digit by digit.
TimsortA hybrid of insertion sort and merge sort; the object sort in Java and Python.

3.1.3Evaluation criteria

Which of two algorithms for the same problem is better depends on what one cares about. Six criteria stand out for sorting algorithms.

Time. The running time of a sorting algorithm is determined largely by the number of two basic operations: comparing two elements and moving elements. A move can be a swap, which exchanges two elements, or a shift, which copies an element from one cell to another. These counts depend not only on the input size n but also on the input itself. So three cases are examined separately: the best case, the average case, and the worst case. Results are stated in asymptotic notation: Θ(n2), Θ(n log n), Θ(n + k), and so on. These complexities count one comparison as O(1); for strings of length L, each comparison can cost O(L) (see Chapters 10–11).

Extra memory. The memory an algorithm uses besides the input array matters too. An algorithm that works with only a few variables, that is, O(1) extra memory, sorts in place. An in-place algorithm rearranges the elements within the input array. Some algorithms, such as merge sort, need auxiliary arrays.

Stability. An algorithm is stable if elements with equal keys keep, in the output, the relative order they had in the input. The next subsection explains this criterion with an example.

Comparison-based or not. Most algorithms in the chapter ask about the elements only one question: "is a ≤ b?" Such algorithms are called comparison sorts. In the worst case a comparison sort must make Ω(n log n) comparisons. Counting sort and radix sort use the key values directly as array indices, so they fall outside this bound.

Adaptivity. An algorithm that sorts a nearly sorted input faster than a random one is adaptive. Insertion sort, bubble sort with a flag, and Timsort are adaptive. Selection sort, by contrast, makes the same number of comparisons whatever the input.

Online operation. An algorithm that can sort elements as they arrive, without seeing all the data in advance, is online. Insertion sort is online: the elements received so far are always sorted, and each new element is inserted in its place. Selection sort is not online, because it must see all elements to find the smallest.

These criteria are independent of one another, and one is often traded for another. Merge sort is both fast and stable but needs extra memory. Heap sort is fast and in place but unstable. No algorithm is best on every criterion; the right one is chosen by what the application needs.

3.1.4Stability

Definition 3.2

A sorting algorithm is stable if, for every two records with equal keys, the record that comes first in the input also comes first in the output. In short, the relative order of records with equal keys is preserved. An algorithm that breaks this condition on at least one input is unstable.

Stability is meaningful only when records have an identity beyond the key. In an array of plain integers, two 3s cannot be told apart, so it does not matter which came first. Figure 3.2 therefore shows the records as (key, label) pairs. Sorting looks only at the number; the letter is the record's identity.

Input(3, A)(1, B)(3, C)(2, D)(1, E)(3, F)3s: ACFStable (insertion)(1, B)(1, E)(2, D)(3, A)(3, C)(3, F)3s: ACFUnstable (selection)(1, B)(1, E)(2, D)(3, C)(3, A)(3, F)3s: CAF
Figure 3.2: A stability example. The input consists of the records (3, A), (1, B), (3, C), (2, D), (1, E), (3, F). Insertion sort leaves the records with key 3 in their input order, A, C, F. The long-distance swaps of selection sort turn that order into C, A, F.
Example 3.1

Here is, step by step, why selection sort (3.4) breaks the order on this input. In each round it finds the smallest element of the unsorted part and swaps it with the first element of the unsorted part.

  1. Round 1. The smallest key is 1; the first 1, that is (1, B), is chosen and swapped with (3, A) at the front. The array is (1, B), (3, A), (3, C), (2, D), (1, E), (3, F). This swap moved (3, A) to index 1.
  2. Round 2. The unsorted part starts at (3, A); the smallest is (1, E), which is swapped with (3, A). The array is (1, B), (1, E), (3, C), (2, D), (3, A), (3, F). Now (3, A) has landed behind (3, C).
  3. Round 3. The smallest is (2, D), swapped with (3, C): (1, B), (1, E), (2, D), (3, C), (3, A), (3, F).
  4. Rounds 4 and 5. The keys of the remaining records are equal, and the code replaces the minimum only on a strictly smaller key, so no swap happens.

In the end the records with key 3 appear in the order C, A, F. The array is correctly sorted by key, but the relative order of A and C has been destroyed. The culprit is the long-distance swap in round 2: (3, A) was sent backward, jumping over (3, C) in between.

Stability is most useful in multi-key sorting. If a student list is sorted first by name and then, with a stable algorithm, by department, each department stays alphabetical. Because the second sort does not touch the order of students in the same department, the alphabetical order built by the first sort survives. An unstable algorithm may scramble the alphabetical order within a department. The same idea underlies radix sort: when numbers are sorted digit by digit, every intermediate step must be stable (3.9.6).

Common mistake

Testing stability on an array of plain integers. There, equal elements are indistinguishable, so even an unstable algorithm looks "correct". Stability is tested with records that have equal keys but different identities, such as the pairs (3, A) and (3, C).

3.2Bubble sort

Bubble sort is one of the first ways one thinks of to sort an array. It looks only at two neighboring elements and swaps them if they are out of order. It is slow in practice, but it shows two important notions clearly: a sorted region that grows from pass to pass, and the inversion. Both reappear in the analysis of insertion sort.

3.2.1The idea

Bubble sort scans the array from left to right and compares two neighboring elements at each step. If the left element is larger than the right one, the two are swapped. A large element is thus carried to the right through successive comparisons, like a bubble rising in water, which is where the algorithm gets its name.

One scan of the array from beginning to end is called a pass. At the end of a pass, the largest element of the part not yet sorted has reached its proper place at the end of the array. The reason is simple: once the scan reaches the largest element, no neighbor is larger, so it is swapped at every comparison, moves one position right each time, and is carried to the end of the pass. After the first pass the largest element is in place, after the second pass the two largest, and in general after pass i the largest i elements are in their final positions. Each pass can therefore be one element shorter than the one before.

Before pass 1: adjacent pairs315264After pass 1132546largest at the end
Figure 3.3: The first pass of bubble sort. At the top, the neighboring pairs being compared are marked with arrows. At the end of the pass, the array 3, 1, 5, 2, 6, 4 becomes 1, 3, 2, 5, 4, 6; the largest element, 6, has settled in the last cell.

A small improvement is possible. If a pass makes no swap, every neighboring pair is in the right order, which means the array is sorted. The remaining passes are then unnecessary and the algorithm can stop early. This information is kept in a flag variable. The version with the flag recognizes a sorted input in a single pass.

3.2.2Step by step: [3, 1, 5, 2, 6, 4]

Let us follow the algorithm on the six-element array [3, 1, 5, 2, 6, 4]. Table 3.2 shows each comparison, its outcome, and the array after the swap. The pair being compared is a[j] and a[j+1].

Table 3.2: All comparisons of bubble sort with a flag on [3, 1, 5, 2, 6, 4].
PassjComparisonResultArray
103 > 1?yes, swap[1, 3, 5, 2, 6, 4]
113 > 5?no[1, 3, 5, 2, 6, 4]
125 > 2?yes, swap[1, 3, 2, 5, 6, 4]
135 > 6?no[1, 3, 2, 5, 6, 4]
146 > 4?yes, swap[1, 3, 2, 5, 4, 6]
201 > 3?no[1, 3, 2, 5, 4, 6]
213 > 2?yes, swap[1, 2, 3, 5, 4, 6]
223 > 5?no[1, 2, 3, 5, 4, 6]
235 > 4?yes, swap[1, 2, 3, 4, 5, 6]
301 > 2?no[1, 2, 3, 4, 5, 6]
312 > 3?no[1, 2, 3, 4, 5, 6]
323 > 4?no[1, 2, 3, 4, 5, 6]

Pass 1 makes five comparisons and three swaps; at the end, 6 sits in its final cell (index 5). Pass 2 is one element shorter: four comparisons, two swaps, and 5 settles at index 4. Pass 3 makes three comparisons and needs no swap in any of them. Because the flag stays false, the algorithm stops here; passes 4 and 5 never start. In total there are 12 comparisons and 5 swaps.

Pass 1jj+1301152236445 Pass 1jj+1103152236445swap End of pass 1103122534465
Figure 3.4: Three moments of the first pass. (a) j = 0: 3 is compared with 1. (b) Since 3 > 1, they were swapped; the array is [1, 3, 5, 2, 6, 4]. (c) End of the pass: 6 has settled in the last cell (green).

3.2.3Java code

The following code sorts the array a of length n with bubble sort and a flag.

boolean swapped;
for(int i = 0; i < n - 1; i++) {
  swapped = false;
  for(int j = 0; j < n - 1 - i; j++) {
    if(a[j] > a[j+1]) {
      int temp = a[j];
      a[j] = a[j+1];
      a[j+1] = temp;
      swapped = true;
    }
  }
  if(swapped == false) break;
}

The code works line by line as follows:

  • The outer loop (i) counts passes. At most n − 1 passes are needed: once n − 1 elements are in place, the one remaining element is automatically in place too.
  • At the start of each pass the swapped flag is set to false. If any swap happens during the pass, it becomes true.
  • The inner loop (j) walks over the neighboring pairs in the unsorted part. The last i elements were placed in earlier passes, so the condition is j < n - 1 - i. The final value of j is n - 2 - i; then a[j+1] is still the last cell of the unsorted part.
  • If a[j] > a[j+1], the two are swapped. A swap takes three assignments: the left value is saved in temp, the right value is written to the left, and the saved value is written to the right. Without temp, the first assignment would destroy the left value.
  • If the flag is still false when a pass ends, no swap occurred in that pass, and break leaves the outer loop.

Note that the condition uses >, not >=. Two equal elements are never exchanged, so the order of elements with equal keys is preserved and bubble sort is stable. The algorithm uses space only for temp, i, j, and the flag: the extra memory is O(1) and the sort is in place.

Common mistake

Writing the inner loop condition as j < n. When j = n - 1, the code tries to read a[j+1], that is, a[n], and Java throws ArrayIndexOutOfBoundsException. In any loop that compares neighboring pairs, the last index is n − 2. Writing j < n - 1 is correct but does unnecessary work; j < n - 1 - i does not look at elements already in place.

3.2.4Code trace: [5, 1, 9, 2, 10]

This time let us run the code on the five-element array [5, 1, 9, 2, 10]. Since n = 5, the outer loop runs at most four passes. Table 3.3 gives the values of the variables at every step.

Table 3.3: Trace of the bubble sort code for a = [5, 1, 9, 2, 10].
ija[j] > a[j+1]swappeda
0—start of passfalse[5, 1, 9, 2, 10]
005 > 1: yes, swaptrue[1, 5, 9, 2, 10]
015 > 9: notrue[1, 5, 9, 2, 10]
029 > 2: yes, swaptrue[1, 5, 2, 9, 10]
039 > 10: notrue[1, 5, 2, 9, 10]
1—start of passfalse[1, 5, 2, 9, 10]
101 > 5: nofalse[1, 5, 2, 9, 10]
115 > 2: yes, swaptrue[1, 2, 5, 9, 10]
125 > 9: notrue[1, 2, 5, 9, 10]
2—start of passfalse[1, 2, 5, 9, 10]
201 > 2: nofalse[1, 2, 5, 9, 10]
212 > 5: nofalse[1, 2, 5, 9, 10]
2—flag false → breakfalse[1, 2, 5, 9, 10]

In the first pass (i = 0) the inner loop runs for j = 0 to 3; two of the four comparisons cause a swap, and at the end 10 is in place. In the second pass (i = 1) the inner loop runs three times under the condition j < 3; 5 and 2 are exchanged and 9 is in place. In the third pass (i = 2) both comparisons answer "no". The flag stays false, so break executes and the fourth pass never starts. The result is [1, 2, 5, 9, 10], with 9 comparisons and 3 swaps in total.

The trace contains an interesting detail: at the end of the second pass the array is in fact sorted, but the algorithm cannot know it. It learns that only when a pass finishes without a swap. So bubble sort with a flag always makes one more pass after the array has become sorted.

3.2.5Analysis and inversions

To understand the cost of bubble sort, let us first define a notion that measures how far an array is from being sorted.

Definition 3.3

An index pair (i, j) with i < j and a[i] > a[j] is called an inversion. An inversion is a pair of elements that are in the wrong order relative to each other; they need not be neighbors.

A sorted array has no inversions. In a reverse-sorted array of n elements, every pair is an inversion; there are n(n − 1)/2 pairs, so that is the number of inversions. Every other array lies between these two extremes.

3152645 inversions[3, 1, 5, 2, 6, 4]
Figure 3.5: The five inversions of the array [3, 1, 5, 2, 6, 4]: (3, 1), (3, 2), (5, 2), (5, 4), and (6, 4). Each arc joins two elements that are in the wrong order relative to each other.
Theorem 3.1 (Adjacent swaps and inversions)

Swapping two adjacent elements that are out of order reduces the number of inversions in the array by exactly one. Hence the number of swaps made by bubble sort equals the number of inversions in the input.

Suppose a[j] > a[j+1] and these two elements are swapped. The two formed an inversion between themselves; after the swap they are in the right order, so that inversion disappears. Now consider any other element x. It lies either to the left or to the right of both elements, and the swap does not change the position of the two elements relative to x. For instance, if x is on the left, it is to the left of both elements before and after. So the inversions involving x stay exactly as they were. The total number of inversions drops by exactly one. Bubble sort makes only such swaps, and a sorted array has no inversions left; therefore the number of swaps equals the initial number of inversions. □

The worst case follows directly from the theorem. A reverse-sorted array has n(n − 1)/2 inversions, so that many swaps are needed. The comparison count is the same: no pass ends early, and the passes make (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 comparisons. In the best case the input is sorted: the flagged version makes n − 1 comparisons in the first pass, no swaps, and stops. In a random permutation, each pair is inverted with probability 1/2; the expected number of inversions, and hence of swaps, is n(n − 1)/4 ≈ n2/4. The number of comparisons is close to n2/2 on average, because the array is usually not sorted until the last passes.

Table 3.4: The cost of bubble sort with a flag.
CaseInputComparisonsSwapsTime
Bestsortedn − 1 (one pass)0Θ(n)
Averagerandom≈ n2/2≈ n2/4Θ(n2)
Worstreverse sortedn(n − 1)/2n(n − 1)/2Θ(n2)

Bubble sort has few advantages, but they are real: it is very easy to understand and write, it is in place and stable, and with a flag it recognizes a sorted input in Θ(n). Its drawbacks weigh more. Quadratic time is unacceptable for large arrays. It performs a separate swap for every inversion, and each swap costs three assignments. Insertion sort, which makes one move per inversion, uses shifts instead of swaps. For this reason bubble sort is always slower than insertion sort in practice and is used mostly for teaching.

Example 3.2

Apply bubble sort with a flag to [5, 2, 4, 6, 1, 3]. The array and the counts at the end of each pass are:

  1. Pass 1 (5 comparisons): 5 ↔ 2, 5 ↔ 4, 6 ↔ 1, and 6 ↔ 3 are swapped; 4 swaps. The array is [2, 4, 5, 1, 3, 6].
  2. Pass 2 (4 comparisons): 5 ↔ 1 and 5 ↔ 3; 2 swaps. The array is [2, 4, 1, 3, 5, 6].
  3. Pass 3 (3 comparisons): 4 ↔ 1 and 4 ↔ 3; 2 swaps. The array is [2, 1, 3, 4, 5, 6].
  4. Pass 4 (2 comparisons): 2 ↔ 1; 1 swap. The array is [1, 2, 3, 4, 5, 6].
  5. Pass 5 (1 comparison): no swap, the flag stays false, break.

In total there are 5 + 4 + 3 + 2 + 1 = 15 comparisons and 4 + 2 + 2 + 1 = 9 swaps. The inversions of the array are (5,2), (5,4), (5,1), (5,3), (2,1), (4,1), (4,3), (6,1), (6,3); there are 9, equal to the number of swaps. Although the array is sorted after the fourth pass, the fifth pass is still needed to find that out.

3.3Insertion sort

Insertion sort is among the fastest known algorithms for small arrays and for nearly sorted ones. It is therefore more than a teaching example: it is also a component of real library algorithms such as Timsort.

3.3.1The idea and the invariant

Insertion sort resembles sorting playing cards in your hand. The cards are taken one at a time, and each new card is placed in its proper position among the sorted cards already held. The cards in hand are sorted at every moment; the sorted part grows by one card at each step.

In an array the idea is applied as follows. The array is divided into two parts: a sorted part on the left and an unsorted part on the right. At the start the sorted part consists of the first element alone; a one-element array is already sorted. At each step the first element of the unsorted part is taken and placed in its proper position within the sorted part. To make room, the elements larger than it are shifted one cell to the right.

next103152236445← sortedunsorted →
Figure 3.6: A moment in insertion sort. The sorted part is 1, 3, 5; the first element of the unsorted part, 2, is about to be inserted into it. For this, 5 and 3 shift one cell to the right and 2 is written to index 1.

The correctness of the algorithm is shown with a loop invariant. An invariant is a statement that is true at the start of every iteration of a loop. The invariant of insertion sort is this: at the start of each step of the outer loop, a[0..i−1] holds the elements originally in those positions, in sorted order. Initially i = 1, and the one-element a[0..0] is sorted. Each step inserts a[i] in its proper place in the sorted part, so a[0..i] becomes sorted and the invariant holds for the next step as well. The loop ends when i = n; at that moment the invariant says that a[0..n−1], the whole array, is sorted.

3.3.2Step by step: [3, 1, 5, 2, 6, 4]

Let us sort the array [3, 1, 5, 2, 6, 4], used earlier for bubble sort, with insertion sort. The element being inserted is held in a variable called key.

Table 3.5: Insertion sort on [3, 1, 5, 2, 6, 4]. Each row is the insertion of one element into the sorted part.
ikeyElements shifted rightInsertion indexShiftsArray
11301[1, 3, 5, 2, 6, 4]
25—20[1, 3, 5, 2, 6, 4]
325, 312[1, 2, 3, 5, 6, 4]
46—40[1, 2, 3, 5, 6, 4]
546, 532[1, 2, 3, 4, 5, 6]

In the first step key = 1. The 3 to its left is larger than 1, so 3 shifts one cell right and we reach the start of the array; 1 is written to index 0. In the second step key = 5; the 3 to its left is smaller, so no element shifts and 5 stays where it is. The third step is longer: for key = 2, first 5 and then 3 shift right; the scan stops at 1 ≤ 2, and 2 is written to index 1. In the fourth step 6 stays in place. In the last step, for 4, the 6 and the 5 shift and 4 lands at index 3. There are 5 shifts in total, a number equal to the number of inversions of the array.

i = 3j103152536445← sortedunsorted →key2 i = 3j+1102132536445← sortedunsorted →
Figure 3.7: Two moments of the third step (i = 3). (a) Since 5 > 2, 5 was shifted one cell right; 5 now appears at both index 2 and index 3, because index 2 has not been overwritten yet. The key box holds 2. (b) 3 has shifted too; since 1 ≤ 2 the scan stops and 2 is placed at index 1.

Moment (a) in Figure 3.7 shows an important point. A shift is a copy: after the assignment a[j+1] = a[j] the same value sits in two cells. This is not an error; the left copy is overwritten in the next step, either by another shift or by key. The original cell of the element being inserted, however, is overwritten by the first shift. That is why the value must be saved in key before the loop starts.

3.3.3Java code

for(int i = 1; i < n; i++) {
  int key = a[i];
  int j = i - 1;
  while(j >= 0 && a[j] > key) {
    a[j+1] = a[j];
    j = j - 1;
  }
  a[j+1] = key;
}
  • The outer loop starts at i = 1 because the one-element a[0..0] is already sorted.
  • key is the element being inserted. The shifts will overwrite its cell, so it is saved first.
  • j starts at the last index of the sorted part (i - 1) and moves left.
  • As long as the element on the left is larger than key, the while loop shifts it one cell right and decrements j. The check j >= 0 in the condition keeps the scan from running past the start of the array. In Java, && short-circuits: when j = -1, the second condition is never evaluated and a[-1] is never read.
  • When the loop ends, either j = -1 or a[j] <= key. In both cases the vacated slot is j + 1, and key is written there.

Insertion sort makes shifts, not swaps. A swap is three assignments; a shift is one. Moving an element k cells to the left costs k swaps, that is, 3k assignments, in bubble sort. In insertion sort, k shifts and two assignments (saving into key and writing it into place), k + 2 assignments in all, suffice. This is why insertion sort is markedly faster than bubble sort.

The condition uses a[j] > key, not >=. On reaching an equal element, the scan stops and the new element lands to the right of the equal one. The input order of equal elements is thus preserved, and insertion sort is stable. The extra memory is only key, i, and j; the algorithm is in place.

Common mistake

Starting to shift without saving the key. If the loop compares directly against a[i] instead of key, the first shift (a[i] = a[i-1]) overwrites the key. From then on the comparisons use the wrong value, and one value in the array is lost while another is duplicated. This is a bug that violates the permutation condition.

3.3.4Code trace: [5, 1, 9, 2, 10]

Let us run the code on the array [5, 1, 9, 2, 10] (n = 5). Table 3.6 shows each while check on its own row.

Table 3.6: Trace of the insertion sort code for a = [5, 1, 9, 2, 10].
ikeyjwhile conditionActiona
1100 ≥ 0 and 5 > 1: truea[1] = 5, j = −1[5, 5, 9, 2, 10]
11−1−1 ≥ 0: falsea[0] = 1[1, 5, 9, 2, 10]
2915 > 9: falsea[2] = 9[1, 5, 9, 2, 10]
3229 > 2: truea[3] = 9, j = 1[1, 5, 9, 9, 10]
3215 > 2: truea[2] = 5, j = 0[1, 5, 5, 9, 10]
3201 > 2: falsea[1] = 2[1, 2, 5, 9, 10]
41039 > 10: falsea[4] = 10[1, 2, 5, 9, 10]

At i = 1, 5 shifts right and j drops to −1. At that point j >= 0 is false and the loop ends; 1 is written to a[0]. At i = 2, the 5 on the left is ≤ 9, so there is no shift; 9 is simply written back into its own cell. At i = 3, 9 and 5 shift, the scan stops at 1 ≤ 2, and 2 goes into a[1]. At i = 4, 10 stays in place. When i = 5, the outer loop condition (5 < 5) is false and the algorithm ends. There are 6 comparisons and 3 shifts in total. The inversions of the array are (5,1), (5,2), (9,2); their number equals the number of shifts.

3.3.5Analysis

In insertion sort, each shift repairs exactly one inversion, formed by the element being inserted and a larger element. So the total number of shifts equals the number of inversions I, just as the number of swaps does in bubble sort. The number of comparisons is at most I + (n − 1). Each successful comparison causes a shift. In addition, each element has at most one failed comparison, the one that ends the loop. If the element slides all the way to the start of the array, that last comparison is not made, because the check j >= 0 becomes false first.

Theorem 3.2 (Running time of insertion sort)

On an array of n elements with I inversions, insertion sort makes exactly I shifts and at most I + n − 1 comparisons. The running time is Θ(n + I).

This theorem shows plainly that insertion sort is adaptive. In a sorted array I = 0: one comparison is made per element, n − 1 in all, and the time is Θ(n). In a reverse-sorted array I = n(n − 1)/2: every element slides to the start of the array and the time is Θ(n2). In a random array the expected I is n(n − 1)/4; the number of comparisons and shifts is about n2/4. That is about half the average number of comparisons of bubble sort.

Table 3.7: The cost of insertion sort.
CaseInputComparisonsShiftsTime
Bestsortedn − 10Θ(n)
Averagerandom≈ n2/4≈ n2/4Θ(n2)
Worstreverse sortedn(n − 1)/2n(n − 1)/2Θ(n2)

Because the best and worst cases grow at different rates, the running time of insertion sort cannot be written as a single Θ for all inputs. The correct statement is: the time is O(n2) and Ω(n) over all inputs; the worst case is Θ(n2) and the best case is Θ(n). An intermediate inference such as "upper bound n2, lower bound n, hence the time is Θ(n log n)" is wrong; the bounds are tight for different families of inputs.

The advantages of insertion sort form a long list: it is stable, in place, online, and adaptive, and its loop is very simple. On small arrays (roughly n ≲ 20–50) its low overhead makes it faster even than n log n algorithms. That is why Timsort and many libraries leave small subarrays to insertion sort inside quicksort and merge sort. Its drawback is quadratic time on large random arrays. The root of this is that an element can advance only one cell per step: a small element at the end of the array needs about n shifts to reach the front. Shell sort was devised precisely to solve this problem (3.5).

Example 3.3

While insertion sort sorts [5, 2, 4, 6, 1, 3], how many times is the comparison a[j] > key made, and how many shifts are performed?

  1. i = 1, key = 2: 5 > 2, shift; j = −1, the condition ends here. 1 comparison, 1 shift. The array is [2, 5, 4, 6, 1, 3].
  2. i = 2, key = 4: 5 > 4, shift; 2 > 4 is false. 2 comparisons, 1 shift. The array is [2, 4, 5, 6, 1, 3].
  3. i = 3, key = 6: 5 > 6 is false. 1 comparison, 0 shifts.
  4. i = 4, key = 1: 6, 5, 4, 2 shift; j = −1. 4 comparisons, 4 shifts. The array is [1, 2, 4, 5, 6, 3].
  5. i = 5, key = 3: 6, 5, 4 shift; 2 > 3 is false. 4 comparisons, 3 shifts. The array is [1, 2, 3, 4, 5, 6].

In total there are 12 comparisons and 9 shifts. The number of shifts equals the number of inversions of the array (9). The number of comparisons is 2 below the bound I + n − 1 = 9 + 5 = 14. The reason: at i = 1 and i = 4 the element slid all the way to the start of the array. In these two steps the loop ended through the j >= 0 check, with no extra comparison.

3.4Selection sort

Selection sort rests on a different principle from bubble sort and insertion sort. It does not move elements a little at a time; in each round it selects the right element and puts it in its final place with a single swap. This approach minimizes the number of swaps, but it keeps the number of comparisons high regardless of the input.

3.4.1The idea

Selection sort also divides the array into a sorted and an unsorted part. At the start the sorted part is empty. Each round does three things:

  1. It finds the smallest element of the unsorted part.
  2. It swaps that element with the first element of the unsorted part.
  3. After the swap, that cell joins the sorted part, which grows by one element.

An element that enters the sorted part is now in its final position. All smaller elements were placed in earlier rounds in the cells to its left, and everything to its right is larger than or equal to it. In this respect selection sort differs from insertion sort. In insertion sort the sorted part is sorted internally, but the elements are not yet in their final places; a small element arriving later may shift all of them. On an array of n elements, n − 1 rounds suffice, because the last remaining element is automatically the largest. Each round makes at most one swap.

minimum102152336445swap← sortedunsorted →
Figure 3.8: One round of selection sort. The sorted part is 1, 2. The smallest element of the unsorted part, 3, is found and swapped with the 5 at the front of the unsorted part.

3.4.2Step by step: [3, 1, 5, 2, 6, 4]

In each round, the first element of the unsorted part is taken as the provisional minimum; the remaining elements are then compared with it one by one. If a smaller element is found, the minimum is updated.

Table 3.8: Selection sort on [3, 1, 5, 2, 6, 4]. The "Scanned" column lists, in order, the elements compared with the provisional minimum.
RoundInitial minimumScannedMinimum foundSwapArray
131, 5, 2, 6, 413 ↔ 1[1, 3, 5, 2, 6, 4]
235, 2, 6, 423 ↔ 2[1, 2, 5, 3, 6, 4]
353, 6, 435 ↔ 3[1, 2, 3, 5, 6, 4]
456, 445 ↔ 4[1, 2, 3, 4, 6, 5]
56556 ↔ 5[1, 2, 3, 4, 5, 6]

In the first round the provisional minimum is 3. Since 1 < 3, the minimum becomes 1; none of the following 5, 2, 6, 4 is smaller than 1. After five comparisons, 1 is swapped with the 3 at the front. In the second round the scan starts from 3 and finds 2; 2 is swapped with the 3 at the front of the unsorted part. Notice that this swap sent 3 to index 3, that is, to the right of 5; in the third round it is selected again and brought to index 2. In the fourth round 4 is swapped with 5, and in the fifth round 5 is swapped with 6. After five rounds the last element, 6, is automatically in place. In total there are 5 + 4 + 3 + 2 + 1 = 15 comparisons and 5 swaps.

Pass 1103152236445swapunsorted →
Figure 3.9: The end of the first round. The minimum found, 1, has been swapped with the 3 at the front of the unsorted part; the thick line is the boundary of the sorted part, and it moves one cell right in the next round.

3.4.3Java code

public void sort(int[] a) {
  int n = a.length;
  for(int i = 0; i < n - 1; i++) {
    int min = i;
    for(int j = i + 1; j < n; j++) {
      if(a[j] < a[min]) {
        min = j;
      }
    }
    int temp = a[min];
    a[min] = a[i];
    a[i] = temp;
  }
}
  • The outer loop runs from i = 0 to n - 2; i is the start of the unsorted part and the cell to be filled in this round.
  • min holds the index of the smallest element found so far, not its value. The swap needs to know which cell to exchange with; the value can always be read as a[min].
  • The inner loop scans the whole unsorted part, from j = i + 1 to the end of the array. Even if the input is sorted, this scan does not get shorter; the only way to confirm that the minimum really is the minimum is to look at every element.
  • The minimum is updated only when a[j] < a[min], that is, on a strictly smaller element. On a tie, the first one found is kept.
  • After the inner loop, a[min] and a[i] are exchanged with three assignments. If min == i, the element is already in place; the code still "swaps it with itself", which is harmless but costs three needless assignments.

Selection sort makes one swap per round, at most n − 1 in total. That is far fewer than the number of swaps in the other simple algorithms. In settings where writing is expensive, for example flash memory where each write wears the cell, the small number of swaps is the one real advantage of selection sort.

Common mistake

Keeping the minimum as a value instead of an index. If you write int minValue = a[i] and update only the value in the inner loop, at the end of the round you do not know which cell holds the minimum, and the swap cannot be made. Since the value can always be read from the index, keeping the index is enough.

3.4.4Code trace: [5, 1, 10, 2, 9]

Table 3.9: Trace of the selection sort code for a = [5, 1, 10, 2, 9]. Each row is one comparison.
ija[j] < a[min]mina at end of round
011 < 5: yes1
0210 < 1: no1
032 < 1: no1
049 < 1: no1a[1] ↔ a[0]: [1, 5, 10, 2, 9]
1210 < 5: no1
132 < 5: yes3
149 < 2: no3a[3] ↔ a[1]: [1, 2, 10, 5, 9]
235 < 10: yes3
249 < 5: no3a[3] ↔ a[2]: [1, 2, 5, 10, 9]
349 < 10: yes4a[4] ↔ a[3]: [1, 2, 5, 9, 10]

At the start of each round min = i is assigned. At i = 0 the minimum is found right away at j = 1, and the next three comparisons do not change it. When j = 5 the inner loop ends and 1 and 5 are exchanged. At i = 1 the minimum is 2 (index 3); at i = 2 it is 5 (again index 3); at i = 3 it is 9 (index 4). For i = 4 the outer loop condition 4 < n − 1 is false and the algorithm ends. In total there are 4 + 3 + 2 + 1 = 10 comparisons and 4 swaps.

3.4.5Analysis and instability

The number of comparisons in selection sort does not depend on the input at all. In round i the inner loop runs n − 1 − i times; the total is

(n − 1) + (n − 2) + … + 1 = n(n − 1)/2

comparisons. Whether the input is sorted, reverse sorted, or random, this many comparisons are made. So the best, average, and worst cases are all the same: Θ(n2). Selection sort is not adaptive; it spends n(n − 1)/2 comparisons even on a sorted array.

Table 3.10: Properties of selection sort.
MeasureValue
Comparisonsn(n − 1)/2, on every input
Swapsat most n − 1
Timebest = average = worst = Θ(n2)
Extra memoryO(1), in place
Stable?No (long-distance swap)

Selection sort is not stable. The reason is that a swap does not merely exchange two elements; it makes one of them jump over all the elements in between. The element at the front of the unsorted part is sent to a distant cell where the minimum was found, and on the way it may jump over an element equal to itself. The smallest example has three elements.

Input2ₐ2ᵦ1Round 1: swapOutput12ᵦ2ₐ
Figure 3.10: The instability of selection sort. The input is [2a, 2b, 1]. In the first round the minimum, 1, is swapped with the 2a at the front, and 2a moves behind 2b. The output is [1, 2b, 2a].

In the second round the unsorted part is [2b, 2a]; since the code updates only on a strictly smaller element, 2b stays in place and no swap occurs. The result is numerically correct, but the relative order of 2a and 2b has been reversed. Selection sort can be made stable: instead of swapping, the minimum is brought to the front by shifting the elements in between one cell right. But that removes the advantage of few swaps and brings the cost close to that of insertion sort.

3.4.6Three simple algorithms on the same input

Bubble, insertion, and selection sort belong to the same quadratic class, but their constant factors and their reactions to the input differ. Table 3.11 gives the comparison and move (swap or shift) counts of the three algorithms on three inputs. The values were obtained by running the code in this chapter; n = 6.

Table 3.11: Cells have the form "comparisons / moves". For bubble and selection sort a move is a swap; for insertion sort it is a shift.
AlgorithmKind of move[3, 1, 5, 2, 6, 4]sorted 1…6reversed 6…1
Bubble (with flag)swap12 / 55 / 015 / 15
Insertionshift9 / 55 / 015 / 15
Selectionswap15 / 515 / 015 / 3

Three observations follow from the table. First, in bubble sort and insertion sort the number of moves equals the number of inversions: 5 for [3, 1, 5, 2, 6, 4] and 6 · 5/2 = 15 for the reversed array. But a swap is three assignments and a shift is one, so the same number of moves is much cheaper in insertion sort. Second, selection sort always makes n(n − 1)/2 = 15 comparisons regardless of the input; in return, it makes the fewest swaps. On the reversed array only 3 swaps suffice: 6 ↔ 1, 5 ↔ 2, and 4 ↔ 3. Elements trade places in pairs, and the swaps in the middle become unnecessary. Third, on a sorted input, bubble sort with a flag and insertion sort make only n − 1 = 5 comparisons; both are adaptive.

The 0 in the swap column of selection sort for the sorted input appears because the count includes only real swaps, those with min ≠ i. As the code is written, it swaps an element with itself in every round; if those are counted as assignments, a sorted input also involves n − 1 "swaps".

3.5Shell sort

The weak point of insertion sort is that an element can advance only one cell per step. Shell sort removes this restriction: it moves elements first in big steps and then in steadily smaller ones. The last pass is ordinary insertion sort again, but by then the array is nearly sorted.

3.5.1The idea and the code

Shell sort, proposed by D. L. Shell in 1959, is a generalization of insertion sort. The algorithm works with a gap value. Elements that are a gap apart form a group: with gap 4, indices 0, 4, 8, … form one group and 1, 5, 9, … another. Each group is sorted internally by insertion sort. In the process a small element jumps a whole gap in one move. Then the gap is reduced and the procedure is repeated. In the last pass the gap is 1, and that pass is ordinary insertion sort.

Since the last pass is insertion sort anyway, why do the earlier passes help? Because they remove most of the distant inversions cheaply. In a pass with gap 4, one shift moves an element four cells; in insertion sort the same move would take four shifts. By the time the gap reaches 1, few inversions remain in the array, and by the theorem in 3.3.5, insertion sort finishes such an array quickly.

void shellSort(int[] a) {
  int n = a.length;
  for (int gap = n / 2; gap > 0; gap /= 2)
    for (int i = gap; i < n; i++) {
      int key = a[i], j;
      for (j = i; j >= gap && a[j - gap] > key; j -= gap)
        a[j] = a[j - gap];
      a[j] = key;
    }
}
  • The outer loop starts the gap at n / 2 and halves it each pass (gap /= 2); it stops when the gap reaches 0. With integer division the gap sequence is 4, 2, 1 for n = 8 and 3, 1 for n = 6.
  • The middle loop runs from i = gap to the end of the array. Each i is the element to be inserted in its own group. The groups are processed interleaved, not one at a time: when i increases by one, the next element belongs to a different group.
  • The inner loop is the same as the while loop of insertion sort, except that the step is gap instead of 1. It stops when j falls below gap or when the group element on the left is not larger than key. key is written to the vacated cell a[j].

Shell sort is in place: it uses only a few variables, so the extra memory is O(1). But it is not stable. Two equal elements can lie in different groups; in a pass with a large gap, one can jump over the other and end up in front of it.

3.5.2Step by step: [6, 5, 3, 1, 8, 7, 2, 4]

For an eight-element array the gap sequence is 4, 2, 1. Table 3.12 gives the state after each gap.

Table 3.12: Shell sort on [6, 5, 3, 1, 8, 7, 2, 4].
gapGroups (before)Groups (after)ShiftsArray
4[6, 8], [5, 7], [3, 2], [1, 4][6, 8], [5, 7], [2, 3], [1, 4]1[6, 5, 2, 1, 8, 7, 3, 4]
2[6, 2, 8, 3], [5, 1, 7, 4][2, 3, 6, 8], [1, 4, 5, 7]6[2, 1, 3, 4, 6, 5, 8, 7]
1[2, 1, 3, 4, 6, 5, 8, 7][1, 2, 3, 4, 5, 6, 7, 8]3[1, 2, 3, 4, 5, 6, 7, 8]

With gap 4 there are four groups of two elements each. Only the group [3, 2] is out of order; one shift makes it [2, 3]. With gap 2 there are two groups: the even indices [6, 2, 8, 3] and the odd indices [5, 1, 7, 4]. The first group becomes [2, 3, 6, 8] under insertion sort (for 2, the 6 shifts; for 3, the 8 and the 6 shift: 3 shifts). The second group also becomes [1, 4, 5, 7] with 3 shifts. When the groups are written back to their places in the array, we get [2, 1, 3, 4, 6, 5, 8, 7]. Only three inversions remain in this array: (2, 1), (6, 5), (8, 7). The gap-1 pass, which is ordinary insertion sort, therefore makes only 3 shifts. Ten shifts were needed in all; sorting the same array directly with insertion sort would have taken as many shifts as there are inversions, namely 16.

gap = 4: groups6051321384752647 gap = 2: after2011324364558677
Figure 3.11: (a) The groups with gap 4: cells of the same color belong to the same group. (b) After the gap-2 pass the array is [2, 1, 3, 4, 6, 5, 8, 7]; the two groups, even and odd indices, are each sorted internally.

3.5.3Code trace: [5, 2, 6, 1, 4, 3]

The behavior of the code on a six-element array is shown in Table 3.13. Since n = 6, the first gap is 3; the groups are the index pairs (0, 3), (1, 4), and (2, 5). The next gap is 3/2 = 1.

Table 3.13: Trace of the Shell sort code for a = [5, 2, 6, 1, 4, 3].
gapikeyInner loopa
331a[0] = 5 > 1: 5 shifts to index 3; stops at j = 0[1, 2, 6, 5, 4, 3]
344a[1] = 2 ≤ 4: no shift[1, 2, 6, 5, 4, 3]
353a[2] = 6 > 3: 6 shifts to index 5; stops at j = 2[1, 2, 3, 5, 4, 6]
112a[0] = 1 ≤ 2: no shift[1, 2, 3, 5, 4, 6]
123a[1] = 2 ≤ 3: no shift[1, 2, 3, 5, 4, 6]
135a[2] = 3 ≤ 5: no shift[1, 2, 3, 5, 4, 6]
144a[3] = 5 > 4: 5 shifts to index 4; stops at a[2] = 3 ≤ 4[1, 2, 3, 4, 5, 6]
156a[4] = 5 ≤ 6: no shift[1, 2, 3, 4, 5, 6]

In the gap-3 pass, 1 jumps from index 3 to index 0 in one move; insertion sort would have needed three shifts for that. In the same way 3 moves from index 5 to index 2. After this pass the array is [1, 2, 3, 5, 4, 6] and only one inversion, (5, 4), remains. The gap-1 pass fixes it with a single shift. When the gap becomes 1/2 = 0, the outer loop ends. Only 3 shifts were made in total. The same array has 9 inversions; insertion sort alone would have made 9 shifts.

3.5.4Gap sequences and complexity

The running time of Shell sort depends on the gap sequence used, and a full analysis is hard. Shell's original sequence is n/2, n/4, …, 1; the code in these notes uses it. The worst case of this sequence is Θ(n2). The cause is that when n is a power of two, all the gaps are even until the last pass. Even indices and odd indices are never compared until the last pass. For example, if all the large elements are at even indices and all the small ones at odd indices, the early passes cannot mix them, and the last pass does quadratic work.

Better gap sequences exist. T. N. Hibbard's sequence 2k − 1 (1, 3, 7, 15, …) keeps consecutive gaps free of common factors and lowers the worst case to O(n1.5). Other sequences improve on this further; in practice Shell sort is quite fast on arrays of moderate size. In the best case, a sorted input, each pass makes about n comparisons and there are log n passes: the time is Θ(n log n). No general closed formula is known for the average running time of Shell sort, so comparison tables list it as "depends on the gaps".

Common mistake

Believing that Shell sort is stable because each group is sorted by insertion sort. Insertion sort is stable within a single group, but two equal elements can be in different groups. For example, in the array [5, 2a, 2b, 1], with gap 2 the even-index group [5, 2b] is sorted and 2b moves to the front; 2a stays in the odd-index group. In the end 2b lands in front of 2a.

3.6Merge sort

All the algorithms examined so far were quadratic in the worst case. Merge sort is the first to break this barrier: it runs in Θ(n log n) time on every input. It does so with a design method that splits a problem into small pieces and combines the solutions of the pieces.

3.6.1Divide and conquer

Divide and conquer is an algorithm design method that splits a problem into smaller subproblems of the same kind, solves the subproblems recursively, and combines the results. Every divide-and-conquer algorithm has three steps.

  1. Divide: The problem is split into smaller subproblems.
  2. Conquer: The subproblems are solved by the same method, recursively. If a subproblem is small enough, it is solved directly; this is the base case of the recursion.
  3. Combine: The solutions of the subproblems are turned into a solution of the original problem.

Merge sort applies this method to sorting. The array is split into two halves at the middle. Each half is sorted by the same method. Then the two sorted halves are merged into a single sorted array. The base case is the one-element array; a one-element array is sorted by definition. The algorithm is attributed to John von Neumann, 1945.

3827433382743327383433273843dividesortmerge
Figure 3.12: The three steps of divide and conquer on [38, 27, 43, 3]. The array is split into the halves [38, 27] and [43, 3]; the halves are sorted separately into [27, 38] and [3, 43]; merging gives [3, 27, 38, 43].

In merge sort the divide step is almost free: only the middle index is computed. The real work is done in the combine step. The idea of merging two sorted arrays is simple. The smallest element of each array is at its front. The two fronts are compared, the smaller is written to the output, and we advance to the next element of that array. When one array runs out, whatever is left in the other is copied to the output in order. Since each comparison writes one element to the output, merging m elements in total takes at most m − 1 comparisons and m writes: the time is Θ(m).

3.6.2Example: [38, 27, 43, 3, 9, 82, 10]

Consider an array of seven elements. Because the middle index is computed as ⌊(lo + hi)/2⌋, in pieces with an odd number of elements the left half takes one extra element: [38, 27, 43, 3] and [9, 82, 10]. Figure 3.13 shows the splits and the merges together.

Input382743398210Divide382743398210Divide382743398210Divide382743398210Merge273834398210Merge327384391082Merge391027384382
Figure 3.13: A merge sort example. In the upper half the array is split down to single elements. In the lower half the pieces are merged in pairs, giving first [27, 38], [3, 43], [9, 82], [10]; then [3, 27, 38, 43] and [9, 10, 82]; and finally [3, 9, 10, 27, 38, 43, 82].

Because the code works depth first, the merges happen not in the level order of the figure but in the order below. The right half is not started before the left half is completely sorted.

Table 3.14: The merge calls of mergeSort(a, 0, 6), in the order they occur.
OrderRangeLeft + rightResultComparisons
1[0..1][38] + [27][27, 38]1
2[2..3][43] + [3][3, 43]1
3[0..3][27, 38] + [3, 43][3, 27, 38, 43]3
4[4..5][9] + [82][9, 82]1
5[4..6][9, 82] + [10][9, 10, 82]2
6[0..6][3, 27, 38, 43] + [9, 10, 82][3, 9, 10, 27, 38, 43, 82]6

merge is called 6 times in all. This number is always n − 1. Each merge reduces two pieces to one, so going from n one-element pieces to a single array takes n − 1 merges. The comparison total is 1 + 1 + 3 + 1 + 2 + 6 = 14.

3.6.3The order of the recursion

To see in what order the recursive calls proceed, let us follow the eight-element array [6, 5, 3, 1, 8, 7, 2, 4]. The array is first split into [6, 5, 3, 1] and [8, 7, 2, 4]. The left half is split into [6, 5] and [3, 1], and [6, 5] into [6] and [5]. The first merge happens here: [6] + [5] → [5, 6]. Then [3, 1] is split and merged as [1, 3]. When [5, 6] and [1, 3] merge, the left half is sorted as [1, 3, 5, 6]. Only after that do we move to the right half: [8, 7] → [7, 8], [2, 4] → [2, 4], and merging the two gives [2, 4, 7, 8]. The last merge is [1, 3, 5, 6] + [2, 4, 7, 8] → [1, 2, 3, 4, 5, 6, 7, 8].

653187241356872456136531 12345678135624785613782465318724
Figure 3.14: The recursion tree. (a) The left half is complete: [5, 6] and [1, 3] merged into [1, 3, 5, 6]; the right half ([8, 7, 2, 4]) has not been touched yet. (b) All merges are done; the root is [1, 2, 3, 4, 5, 6, 7, 8]. Green boxes are sorted pieces.

This order is the natural consequence of keeping the recursive calls on a stack, the call stack. At any moment the stack holds at most ⌈log2 n⌉ + 1 calls, because each call halves the piece size. For eight elements the stack depth is at most 4: four pieces of sizes 8, 4, 2, and 1.

3.6.4Java code

The code consists of two methods. mergeSort sorts the range a[lo..hi]; the initial call for the whole array is mergeSort(a, 0, n - 1).

void mergeSort(int[] a, int lo, int hi) {
  if (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);
    merge(a, lo, mid, hi);
  }
}
  • If lo < hi does not hold, the range has at most one element and the method returns without doing anything; this is the base case.
  • The middle index is computed as lo + (hi - lo) / 2. In mathematics this equals (lo + hi) / 2. But in Java the sum lo + hi can exceed the int limit (231 − 1) on very large arrays and wrap around to a negative number. The first form avoids this overflow.
  • The left half [lo..mid] and the right half [mid+1..hi] are sorted recursively; then merge is called.

merge merges the sorted pieces A[p..q] and A[q+1..r] into A[p..r].

void merge(int[] A, int p, int q, int r) {
  int[] L = Arrays.copyOfRange(A, p, q + 1);
  int[] R = Arrays.copyOfRange(A, q + 1, r + 1);
  int i = 0, j = 0, k = p;
  while (i < L.length && j < R.length) {
    if (L[i] <= R[j]) A[k++] = L[i++];
    else              A[k++] = R[j++];
  }
  while (i < L.length) A[k++] = L[i++];
  while (j < R.length) A[k++] = R[j++];
}
  • The two halves are first copied into the auxiliary arrays L and R with Arrays.copyOfRange. The copy is necessary because the result is written directly into the same cells of A, and without a copy it would overwrite elements not yet read. The upper bound of copyOfRange is exclusive, which is why q + 1 and r + 1 are written.
  • i and j point to the next element of L and R respectively, and k to the cell of A to be written.
  • The first while compares the fronts as long as both arrays have elements; it writes the smaller or equal one to A[k] and advances the corresponding index. The expression A[k++] = L[i++] first writes, then increments both indices.
  • When one array runs out, only one of the remaining two while loops runs and copies what is left of the other array in order. The remaining elements are already sorted and are greater than or equal to everything written so far; no comparison is needed.

The condition is L[i] <= R[j]. On a tie the left element is taken first. Since elements in the left half came before those in the right half in the input, the relative order of equal keys is preserved: merge sort is stable.

Common mistake

Writing < instead of <= in the merge. The array is still sorted correctly, but on a tie the right element is taken first. The order of two records with equal keys is reversed and the algorithm loses its stability. This bug does not show up in tests with arrays of numbers; it appears only when records are sorted.

3.6.5Code trace: merge()

In the last step of the [6, 5, 3, 1, 8, 7, 2, 4] example, merge(A, 0, 3, 7) is called. At that moment A[0..3] = [1, 3, 5, 6] and A[4..7] = [2, 4, 7, 8].

Table 3.15: Trace of merge for L = [1, 3, 5, 6], R = [2, 4, 7, 8].
Stepi, j, kComparisonWrittenA[0..k]
10, 0, 0L[0] = 1 ≤ R[0] = 2A[0] = 1[1]
21, 0, 1L[1] = 3 > R[0] = 2A[1] = 2[1, 2]
31, 1, 2L[1] = 3 ≤ R[1] = 4A[2] = 3[1, 2, 3]
42, 1, 3L[2] = 5 > R[1] = 4A[3] = 4[1, 2, 3, 4]
52, 2, 4L[2] = 5 ≤ R[2] = 7A[4] = 5[1, …, 5]
63, 2, 5L[3] = 6 ≤ R[2] = 7A[5] = 6[1, …, 6]
74, 2, 6L is exhausted; the rest of R is copiedA[6] = 7[1, …, 7]
84, 3, 7—A[7] = 8[1, …, 8]

In the first six steps one comparison is made each, and the result comes alternately from the two arrays. After step six i = 4; L is exhausted and the first while ends. The remaining 7 and 8 are copied without comparison. There are 6 comparisons and 8 writes in total. Merging eight elements takes at most 7 comparisons; the bound is reached when the two arrays run out together at their last elements. For example, L = [1, 3, 5, 7], R = [2, 4, 6, 8] needs 7 comparisons.

L1356iR2478jA10213234567k
Figure 3.15: The state after the third step. 1 and 3 have been taken from L and 2 from R (faded cells). The next comparison is between L[2] = 5 and R[1] = 4; k = 3.

3.6.6Analysis

The running time of merge sort is expressed with a recurrence. Let T(n) be the time to sort an array of n elements. The algorithm solves two subproblems of size n/2 and merges the results in Θ(n) time. The divide step takes constant time. This gives the recurrence

T(n) = 2 T(n/2) + Θ(n), T(1) = Θ(1)

The most intuitive way to solve this recurrence is the recursion tree. At the root there is one problem of size n, and the merge work is n. One level down there are two problems of size n/2; each does n/2 work, and the level's total is again n. One more level down there are four of size n/4; the total is again n. At each level the number of pieces doubles, the piece size halves, and the total work stays the same. There are log2 n levels until the piece size drops to 1. The total work is n per level times the number of levels, that is, n log2 n.

nnn/2n/2nn/4n/4n/4n/4n⋮⋮11111111nΣ = n · log₂ nlog₂ n levels
Figure 3.16: The recursion tree of merge sort. The total merge work at each level is n; there are log2 n levels, and the total is n · log2 n.

The same result follows from the master theorem. The recurrence has the form T(n) = aT(n/b) + f(n), here with a = 2, b = 2, and f(n) = Θ(n). We get nlogb a = nlog2 2 = n, and f(n) = Θ(nlogb a) is the second case of the theorem. In this case T(n) = Θ(nlogb a log n) = Θ(n log n).

Merge sort does not look at the arrangement of the input; in every case it splits the array the same way and performs the same merges. So the best, average, and worst cases coincide: Θ(n log n). The number of comparisons varies a little with the input, because when one array ends early the rest is copied without comparison, but this variation does not affect the growth rate.

As for extra memory, merge sort is not in place. During a merge, L and R together hold n elements; the extra memory is Θ(n). To this are added the Θ(log n) frames of the recursion stack. For large data sets this extra memory is a significant cost, and it is one of the reasons quicksort is preferred in practice.

Example 3.4

What is the maximum number of comparisons merge sort needs to sort an 8-element array?

  1. Levels. For 8 elements the recursion tree has three levels of merging: four merges of 2 elements, two merges of 4 elements, and one merge of 8 elements.
  2. One merge. Merging m elements takes at most m − 1 comparisons: each comparison writes one element, and the last element is written without a comparison.
  3. Total. 4 · 1 + 2 · 3 + 1 · 7 = 4 + 6 + 7 = 17.

The answer is 17. When the code is run on all 8! = 40,320 permutations, the maximum number of comparisons is indeed 17. The rough upper estimate is n log2 n = 24; compared with the n(n − 1)/2 = 28 comparisons of the simple algorithms, the difference shows even at small n.

A by-product of merge sort is counting inversions. When an element is taken from R during a merge, all the elements remaining in L are larger than it, and each forms an inversion with it. We add L.length − i to a counter. The inversions within the left and right halves are counted recursively. The total work is the same as for merge sort: Θ(n log n). The brute-force method, which checks every pair, takes Θ(n2). For example, in the array [3, 1, 2, 5, 4] the inversions are (3, 1), (3, 2), and (5, 4); there are 3.

3.7Quicksort

Quicksort also uses divide and conquer, but it moves the work to a different place. In merge sort, dividing is easy and merging is hard. In quicksort, dividing is hard and no merging is needed at all. It is Θ(n log n) on average, works in place, and is cache-friendly; for these reasons it is usually the fastest comparison sort in practice.

3.7.1The idea

Quicksort is an algorithm that C. A. R. Hoare developed in 1959 and published in 1961–1962. It consists of three steps:

  1. A pivot element is chosen from the array. Call the pivot x.
  2. The array is split around the pivot into two parts: elements less than or equal to x on the left, elements greater than or equal to x on the right. The pivot is placed between the two. This operation is called partitioning.
  3. The two parts are sorted recursively.
≤ xx≥ xpivotleft part → sort recursivelyright part → sort recursively
Figure 3.17: The array after partitioning: elements less than or equal to the pivot on the left, the pivot x in the middle, elements greater than or equal to it on the right. The left and right parts are sorted separately, recursively.

Partitioning has an important consequence: after partitioning, the pivot is in its final position. All elements to its left are less than or equal to it and those to its right are greater than or equal to it; in the sorted array it will stand at exactly that index. When the two parts are sorted, elements never cross the boundary between the parts. So no extra work is needed to combine the two sorted parts: the array is sorted in place.

3.7.2The partition procedure

There are several ways to partition. These notes use the method named after N. Lomuto. The last element of the range is chosen as the pivot, and the array is scanned in a single pass.

partition(A, p, q):
  pivot = A[q]        // choose the pivot
  i = p - 1           // end of the "<= pivot" region
  for j = p to q - 1:
    if A[j] <= pivot:
      i = i + 1
      swap(A[i], A[j])
  swap(A[i + 1], A[q])  // put the pivot in place
  return i + 1          // index of the pivot

The procedure works with two indices. i is the last cell of the "less than or equal to the pivot" region; the region is empty at first, so i = p − 1. j is the next element to examine. At each step A[j] is compared with the pivot. If it is larger, only j advances; the element has joined the "larger" region. If it is smaller or equal, i is incremented and A[i] and A[j] are swapped. The element is thereby taken to the end of the smaller region, and the first element of the larger region moves into j's place. When the scan ends, the pivot is swapped with A[i + 1], the first cell of the larger region, and its index is returned.

The correctness of the procedure rests on the following loop invariant: at the start of each step,

  • the elements in A[p..i] are less than or equal to the pivot,
  • the elements in A[i+1..j−1] are greater than the pivot,
  • A[j..q−1] has not yet been examined and A[q] is the pivot.

Initially the first two regions are empty and the invariant holds trivially. Each step preserves the invariant by adding the examined element to the right region. When the loop ends, the unexamined region is empty, and moving the pivot to A[i+1] puts the array in the desired form. The scan is a single pass: for a range of n elements it makes n − 1 comparisons, the time is Θ(n), and the extra memory is O(1).

The same idea can be implemented with the first element as the pivot. In this version the pivot stays in A[p], the scan starts at p + 1, and at the end the pivot is swapped with the last element of the smaller region.

PARTITION(A, p, q):
  x = A[p]            // pivot
  i = p
  for j = p + 1 to q:
    if A[j] <= x:
      i = i + 1
      swap(A[i], A[j])
  swap(A[p], A[i])
  return i

3.7.3Partition example: the first element as pivot

Let us trace the version that takes the first element as the pivot on the array [6, 10, 13, 5, 8, 3, 2, 11]. The pivot is x = 6; i = p = 0, and j starts at 1.

Table 3.16: Partitioning [6, 10, 13, 5, 8, 3, 2, 11] with PARTITION (first element as pivot).
jA[j]A[j] ≤ 6?iArray
110no0[6, 10, 13, 5, 8, 3, 2, 11]
213no0[6, 10, 13, 5, 8, 3, 2, 11]
35yes: A[1] ↔ A[3]1[6, 5, 13, 10, 8, 3, 2, 11]
48no1[6, 5, 13, 10, 8, 3, 2, 11]
53yes: A[2] ↔ A[5]2[6, 5, 3, 10, 8, 13, 2, 11]
62yes: A[3] ↔ A[6]3[6, 5, 3, 2, 8, 13, 10, 11]
711no3[6, 5, 3, 2, 8, 13, 10, 11]
last—A[0] ↔ A[3]3[2, 5, 3, 6, 8, 13, 10, 11]

During the scan, the front of the array is divided into three regions: the pivot, the smaller region, and the larger region. The first two elements (10 and 13) are larger and join the larger region. When 5 arrives, the smaller region grows by one and 5 is swapped with 10, the first element of the larger region. The same happens for 3 and 2. When the scan ends, i = 3. The pivot is swapped with 2, the last element of the smaller region. In the end the pivot 6 settles at index 3; the 2, 5, 3 to its left are smaller and the 8, 13, 10, 11 to its right are larger. Note that the parts are not sorted internally; partitioning only puts the pivot in place.

j = 3ij6051132103843526117swap Last: A[p] ↔ A[i]i2051326384135106117swap
Figure 3.18: (a) j = 3: since 5 ≤ 6, i becomes 1 and A[1] and A[3] are swapped. Blue: ≤ pivot, red: > pivot, white: not yet examined. (b) The final swap: the pivot 6 trades places with the last element of the smaller region and lands at index 3.

3.7.4Code trace: partition()

The Java version of Lomuto partitioning follows. swap(a, x, y) is a helper method that exchanges the values of two cells with three assignments.

int partition(int[] a, int lo, int hi) {
  int pivot = a[hi];
  int i = lo - 1;
  for (int j = lo; j < hi; j++) {
    if (a[j] <= pivot) {
      i++;
      swap(a, i, j);
    }
  }
  swap(a, i + 1, hi);
  return i + 1;
}

Let us trace the method on [2, 8, 7, 1, 3, 5, 6, 4] with the call partition(a, 0, 7). The pivot is a[7] = 4 and initially i = −1.

Table 3.17: Trace of partition(a, 0, 7), a = [2, 8, 7, 1, 3, 5, 6, 4].
ja[j] ≤ 4?iActiona
02: yes0swap(0, 0) (with itself)[2, 8, 7, 1, 3, 5, 6, 4]
18: no0—[2, 8, 7, 1, 3, 5, 6, 4]
27: no0—[2, 8, 7, 1, 3, 5, 6, 4]
31: yes1swap(1, 3)[2, 1, 7, 8, 3, 5, 6, 4]
43: yes2swap(2, 4)[2, 1, 3, 8, 7, 5, 6, 4]
55: no2—[2, 1, 3, 8, 7, 5, 6, 4]
66: no2—[2, 1, 3, 8, 7, 5, 6, 4]
last—2swap(3, 7), return 3[2, 1, 3, 4, 7, 5, 6, 8]

The first element, 2, is smaller than the pivot; i becomes 0 and the element is swapped with itself. This is harmless but an unnecessary swap. 8 and 7 are larger and only j advances. When 1 arrives, i = 1 and 1 is swapped with 8, the first element of the larger region. The same happens for 3: 3 and 7 trade places. 5 and 6 are larger. The loop ends at j = hi; the pivot is moved to index i + 1 = 3 and 3 is returned. The elements in the left part [0..2] are smaller than 4, and those in the right part [4..7] are larger than 4. There are 7 comparisons in all, which is n − 1 = 7 for a range of 8 elements.

3.7.5The recursive structure

Once partitioning is available, quicksort itself is a few lines. The pseudocode is written with 1-based indices:

QUICKSORT(A, p, r)
  if p < r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q − 1)
    QUICKSORT(A, q + 1, r)

Initial call: QUICKSORT(A, 1, n)

The Java version is 0-based, and the initial call for the whole array is quickSort(a, 0, n - 1).

void quickSort(int[] a, int lo, int hi) {
  if (lo < hi) {
    int p = partition(a, lo, hi);
    quickSort(a, lo, p - 1);
    quickSort(a, p + 1, hi);
  }
}
≤ pivot: lo … p − 1p> pivot: p + 1 … hiquickSort(a, lo, p − 1)quickSort(a, p + 1, hi)in place
Figure 3.19: After the partition call, the pivot is at index p, in its final place. The left part lo … p − 1 and the right part p + 1 … hi are sorted by two separate recursive calls.

Two points in the code deserve attention. First, the pivot is included in neither recursive call; the calls end at p − 1 and start at p + 1. The pivot has settled in its place and is never touched again. Second, the base case is that the condition lo < hi is false: the range has zero or one element, and such a range is already sorted. When the pivot is the smallest or the largest of its part, an empty part results; for example quickSort(a, 0, -1). That call returns immediately.

Common mistake

Including the pivot in the recursion, that is, writing quickSort(a, lo, p). If the pivot is the largest of its part, the left part is again the entire range and never shrinks. For example, in a sorted two-element range the pivot is the largest, the left part is again two elements, and the same call repeats forever. The result is a StackOverflowError.

3.7.6A complete run: [6, 10, 13, 5, 8, 3, 2, 11]

Table 3.16 showed only the first partition. Let us trace the whole sort, again with the first element as pivot, together with the depth of the recursion.

Table 3.18: Quicksort of [6, 10, 13, 5, 8, 3, 2, 11] (first element as pivot). The rows are in the order the calls occur.
DepthRangePiecePivot → indexNext calls
0[0..7][6, 10, 13, 5, 8, 3, 2, 11]6 → 3[0..2], [4..7]
1[0..2][2, 5, 3]2 → 0[0..−1], [1..2]
2[1..2][5, 3]5 → 2[1..1], [3..2]
3[1..1][3]base case—
1[4..7][8, 13, 10, 11]8 → 4[4..3], [5..7]
2[5..7][13, 10, 11]13 → 7[5..6], [8..7]
3[5..6][11, 10]11 → 6[5..5], [7..6]
4[5..5][10]base case—

In the table, empty ranges (such as [0..−1] and [3..2]) are not listed as separate rows; those calls return immediately. When all calls are finished, the array is [2, 3, 5, 6, 8, 10, 11, 13]. There is no merge step: each pivot settled in its own partitioning, and the parts were sorted in place. On the right side the recursion goes four levels deep, because the pivots 8 and 13 are the smallest and the largest of their parts; each splits off only itself from its part.

QUICKSORT(A, 0, 7)q2051326384135106117
Figure 3.20: The array after the partition at depth 0. The pivot 6 has settled at index 3 (q); the blue left part [0..2] and the red right part [4..7] will be sorted separately.

3.7.7Call trace: [5, 2, 8, 1, 9, 3]

The calls of the Java code (last element as pivot) on a six-element array are given in order in the table below. Each row is one quickSort call.

Table 3.19: Trace of the calls of quickSort(a, 0, 5), a = [5, 2, 8, 1, 9, 3].
CallStatusPivot → pa (after the call)
(0, 5)lo < hi3 → 2[2, 1, 3, 5, 9, 8]
(0, 1)lo < hi1 → 0[1, 2, 3, 5, 9, 8]
(0, −1)empty part, base case—unchanged
(1, 1)one element, base case—unchanged
(3, 5)lo < hi8 → 4[1, 2, 3, 5, 8, 9]
(3, 3)one element, base case—unchanged
(5, 5)one element, base case—unchanged

In the first call the pivot is 3; the elements smaller than 3, namely 2 and 1, are gathered on the left, 5, 9, 8 stay on the right, and the pivot settles at index 2. Then the left part (0, 1) is sorted: pivot 1, empty left, right [2]. Empty and one-element parts return immediately. When the left side is done, the second recursive line of the first call runs and (3, 5) is called: pivot 8, with [5] on its left and [9] on its right. There are 3 partition calls and 4 base-case calls in all; the result is [1, 2, 3, 5, 8, 9].

102132538495array(0, 5)(0, 1)(3, 5)(0, -1)(1, 1)(3, 3)(5, 5)
Figure 3.21: The quickSort call tree. The root is (0, 5), with children (0, 1) and (3, 5); the leaves are base-case calls on empty or one-element parts. The sorted array is shown at the top.

3.7.8Analysis and pivot choice

The running time of quicksort depends on how evenly the pivot splits the array. Each partition does work linear in the size of the range. The balance of the splits determines the depth of the recursion tree.

Best case. If the pivot is the median of its part every time, the array splits into two equal halves. The recurrence is the same as for merge sort: T(n) = 2T(n/2) + Θ(n), with solution Θ(n log n).

Worst case. If the pivot is the smallest or the largest of its part every time, one part is empty and the other has n − 1 elements. The recurrence becomes T(n) = T(n − 1) + Θ(n). Unrolled, it gives n + (n − 1) + … + 1, that is, Θ(n2). Surprisingly, this happens on the "easiest" input: on an already sorted array, the version that takes the last element as pivot picks the largest every time. On a sorted array of 1000 elements the number of comparisons is 999 + 998 + … + 1 = 499,500, and the recursion goes 1000 levels deep. On very large arrays this depth overflows the call stack and gives a StackOverflowError.

Average case. On a random input the pivot usually lands "central enough". Even in the bad-looking case where the pivot always splits 1 to 9, the depth of the recursion tree is log10/9 n, which is still logarithmic; the total work stays O(n log n). A detailed analysis shows that the expected number of comparisons is about 2n ln n ≈ 1.39 n log2 n for large n. For small n the lower-order terms matter as well. The exact expected value for Lomuto partitioning is 2(n + 1)Hn − 4n (Hn is the harmonic number), which comes to about 10,986 for n = 1000. That is about 26% more than the number of comparisons of merge sort. Even so, quicksort is usually faster in practice: its inner loop is very simple, it copies no auxiliary array, and because it scans the array sequentially it uses the processor cache well.

Table 3.20: The cases of quicksort.
CaseWhen?RecurrenceTime
Bestpivot is the median every timeT(n) = 2T(n/2) + Θ(n)Θ(n log n)
Averagerandom input or random pivotexpected ≈ 1.39 n log2 n comparisonsΘ(n log n)
Worstpivot is always the smallest or the largest (e.g., sorted array with the last element as pivot)T(n) = T(n − 1) + Θ(n)Θ(n2)

To avoid the worst case, the choice of pivot is improved.

  • Random pivot. The pivot is chosen at random from the range and swapped with the last cell before partitioning. No fixed input can then produce the worst case every time; Θ(n2) happens only with very small probability, through unlucky random choices. The expected time is Θ(n log n) on every input.
  • Median of three. The median of the first, middle, and last elements becomes the pivot. On sorted and reverse-sorted inputs this choice gives exactly the middle and prevents the bad case, but on specially constructed inputs it can still be Θ(n2).
  • Small parts. When the part size becomes small (roughly n ≲ 16), switching to insertion sort speeds things up in practice. Also, if one recurses on the smaller part first and handles the larger part with a loop, the recursion depth stays O(log n) even in the worst case.

Quicksort is in place: it uses extra memory only for the recursion stack, O(log n) on average. It is not stable; the long-distance swaps in partitioning can disturb the order of equal elements. Java's Arrays.sort(int[]) uses a version of quicksort with two pivots (dual-pivot quicksort) on primitive arrays. Stability does not matter for primitive types, because two equal int values cannot be told apart.

Common mistake

Saying "quicksort is always n log n". With a fixed pivot rule (first or last element), sorted and reverse-sorted inputs give Θ(n2) time and a recursion of depth n. In real applications data often arrives partly sorted, so this case is not merely theoretical; use a random pivot or median of three.

3.8Heap sort

Merge sort is Θ(n log n) even in the worst case but needs extra memory. Quicksort is in place but quadratic in the worst case. Heap sort combines the good sides of both: it takes O(n log n) time in the worst case and works in place with O(1) extra memory. It does so by using the array itself as a data structure.

3.8.1The heap and its array representation

A heap is a complete binary tree, with every level full except possibly the last, which is filled from left to right, and it satisfies an ordering condition. In a max-heap every node is greater than or equal to its children. Since this holds everywhere in the tree, the largest element is at the root. The heap is familiar from data structures as the priority queue; here we look only at how it is used in sorting.

The most useful property of a heap is that the tree need not be stored as a separate structure. A complete binary tree is stored in an array level by level, from left to right. With 0-based indices, the left child of a[i] is at 2i + 1, the right child at 2i + 2, and the parent at (i − 1) / 2 (integer division). It is therefore possible to move around the tree with index arithmetic alone, without pointers. This is exactly why heap sort is in place: the array to be sorted is itself the heap.

1005132431410051324314array
Figure 3.22: The max-heap [10, 5, 3, 4, 1] as a tree and as an array. The root is 10 (index 0); its children are 5 (index 1) and 3 (index 2), and the children of 5 are 4 (index 3) and 1 (index 4). The small numbers next to the nodes are array indices.

Heap sort works in two phases:

  1. The array is turned into a max-heap.
  2. The root, that is, the largest element, is swapped with the last element of the heap. That element now belongs to the sorted region at the end of the array, and the heap shrinks by one. Since the element that arrived at the root may violate the heap condition, it sinks down and the heap is restored. This step is repeated until one element is left in the heap.

Both phases rest on the same operation: sifting a node down. If the node is smaller than one of its children, it is swapped with its larger child, and the same check is repeated at its new position. Sifting ends when the node is greater than or equal to both children or when it reaches a leaf. The precondition for this operation is that both subtrees of the node are already heaps.

3.8.2Example: [4, 10, 3, 5, 1]

Let us see the whole algorithm on a small array. Table 3.21 shows, at each step, the heap part and the sorted part of the array separately.

Table 3.21: Sorting [4, 10, 3, 5, 1] with heap sort. In the array column a vertical bar separates the heap from the sorted region.
StepArray (heap | sorted)Explanation
Input[4, 10, 3, 5, 1]not a heap yet
Build max-heap[10, 5, 3, 4, 1]the root is the largest element
Root ↔ a[4][1, 5, 3, 4 | 10]10 moved to the sorted region
Restore max-heap[5, 4, 3, 1 | 10]1 sifted down (1 ↔ 5, 1 ↔ 4)
Root ↔ a[3][1, 4, 3 | 5, 10]5 moved to the sorted region
Restore max-heap[4, 1, 3 | 5, 10]1 sifted down (1 ↔ 4)
Root ↔ a[2][3, 1 | 4, 5, 10]4 moved to the sorted region
Restore max-heap[3, 1 | 4, 5, 10]3 is already larger; no change
Root ↔ a[1][1 | 3, 4, 5, 10]3 moved to the sorted region
Result[1, 3, 4, 5, 10]the one-element heap is in place too

In the heap-building step, the non-leaf nodes are processed from bottom to top. The 10 at index 1 is larger than its children (5 and 1); nothing changes. The 4 at the root is swapped with its larger child, 10. At its new position (index 1) its children are 5 and 1; 4 is swapped with 5 and sinks to a leaf. The result is [10, 5, 3, 4, 1]. In each later round the largest element of the heap is moved to the end; the sorted region fills from right to left, from largest to smallest.

410351build heap105341[4, 10, 3, 5, 1]max-heap
Figure 3.23: The tree of [4, 10, 3, 5, 1] turning into the max-heap [10, 5, 3, 4, 1]. In the upper tree the root 4 is smaller than its child 10; in the lower tree every parent is larger than its children.

3.8.3Phase one: building a max-heap

Consider the eight-element array [6, 5, 3, 1, 8, 7, 2, 4]. Viewed as a complete binary tree, it is not yet a heap: for example, the 5 at index 1 is smaller than its child 8.

The efficient way to build a heap is to work from the bottom up. The leaves (index ⌊n/2⌋ and beyond, here 4–7) are one-element heaps already; nothing needs to be done with them. Processing starts at the last internal node, index n/2 − 1 = 3, and proceeds toward the root. Each node is sifted down. When a node is processed, its two subtrees have been processed earlier, so they are already heaps; the precondition of sifting is therefore always met.

Table 3.22: Bottom-up max-heap construction on [6, 5, 3, 1, 8, 7, 2, 4].
StepNodeSwapsArray
heapify(3)1 (child 4)1 ↔ 4[6, 5, 3, 4, 8, 7, 2, 1]
heapify(2)3 (children 7, 2)3 ↔ 7[6, 5, 7, 4, 8, 3, 2, 1]
heapify(1)5 (children 4, 8)5 ↔ 8[6, 8, 7, 4, 5, 3, 2, 1]
heapify(0)6 (children 8, 7)6 ↔ 8[8, 6, 7, 4, 5, 3, 2, 1]

After the 6 at the root is swapped with its larger child 8, it sinks to index 1. There its children are 4 and 5; since 6 is larger than both, the sifting stops. When all internal nodes have been processed, the array is [8, 6, 7, 4, 5, 3, 2, 1]. This is a max-heap, and the largest element, 8, is at the root. Note that a heap is not a sorted array; it only guarantees that every parent is larger than its children.

60513213847526476051321384752647array 80617243543526178061724354352617array
Figure 3.24: (a) The start: [6, 5, 3, 1, 8, 7, 2, 4] as a complete binary tree; not yet a heap. (b) After the non-leaf nodes (indices 3, 2, 1, 0) are processed, the max-heap [8, 6, 7, 4, 5, 3, 2, 1]; the largest element is at the root.

3.8.4Phase two: moving the root to the end

The max-heap [8, 6, 7, 4, 5, 3, 2, 1] is ready. In each round the root is swapped with the last element of the heap; the heap shrinks by one and the element that arrived at the root sifts down.

Table 3.23: The second phase of heap sort. The "Sift" column gives the swaps made by the element that arrived at the root.
RoundRoot ↔ lastSiftHeapSorted region
18 ↔ 11 ↔ 7, 1 ↔ 3[7, 6, 3, 4, 5, 1, 2][8]
27 ↔ 22 ↔ 6, 2 ↔ 5[6, 5, 3, 4, 2, 1][7, 8]
36 ↔ 11 ↔ 5, 1 ↔ 4[5, 4, 3, 1, 2][6, 7, 8]
45 ↔ 22 ↔ 4[4, 2, 3, 1][5, 6, 7, 8]
54 ↔ 11 ↔ 3[3, 2, 1][4, 5, 6, 7, 8]
63 ↔ 11 ↔ 2[2, 1][3, 4, 5, 6, 7, 8]
72 ↔ 1—[1][2, 3, 4, 5, 6, 7, 8]

In round 1, 8 moves to the last cell (index 7) and 1 arrives at the root. The children of 1 are 6 and 7; it is swapped with the larger, 7, and sinks to index 2. There its children are 3 and 2; it is swapped with 3 and reaches a leaf. The heap is [7, 6, 3, 4, 5, 1, 2]. The later rounds proceed in the same way. After seven rounds one element is left in the heap; it is the smallest and is in place at index 0. The sorted array is [1, 2, 3, 4, 5, 6, 7, 8].

106172435435261061724354352687array 706132435415267061324354152687array
Figure 3.25: Round 1 of the second phase. (a) The root 8 has been swapped with a[7] = 1; 8 has moved to the sorted region (green), and the heap size is 7. (b) The 1 at the root has sifted down (1 ↔ 7, 1 ↔ 3); the heap is [7, 6, 3, 4, 5, 1, 2].

3.8.5Java code and analysis

void heapSort(int[] a) {
  int n = a.length;
  for (int i = n / 2 - 1; i >= 0; i--)   // 1) build the heap
    heapify(a, n, i);
  for (int i = n - 1; i > 0; i--) {      // 2) sort
    swap(a, 0, i);                       // max to the end
    heapify(a, i, 0);                    // sift the root
  }
}
void heapify(int[] a, int n, int i) {
  while (true) {
    int largest = i, left = 2 * i + 1, right = 2 * i + 2;
    if (left < n && a[left] > a[largest]) largest = left;
    if (right < n && a[right] > a[largest]) largest = right;
    if (largest == i) return;         // in place
    swap(a, i, largest);
    i = largest;                       // keep sinking
  }
}
  • heapSort consists of two loops. The first builds the heap: i decreases from the last internal node n / 2 - 1 to the root, and heapify(a, n, i) is called for each node.
  • The second loop sorts: i decreases from the last index to 1. In each round the root is swapped with a[i]. Then heapify(a, i, 0) is called; the second argument i says that the heap now consists only of the first i elements. The elements already moved to the end are thus not reused in sifting.
  • heapify sifts node i down in a heap of size n. First the index of the largest among i and its left and right children is found in largest. The checks left < n and right < n ask whether the child is inside the heap.
  • If largest == i, the node is in place and the method returns. If not, the node is smaller than one of its children; the two are swapped, i = largest is set, and the while loop continues sifting at the child's position.

The cost of building the heap. The build loop sifts about n/2 nodes, and a single sift takes O(log n). This gives a crude O(n log n) bound. But the bound is loose, because most nodes are low in the tree. A node of height h sifts at most h steps. The number of nodes of height h is at most ⌈n/2h+1⌉: there are about n/2 leaves, n/4 nodes one level up, and so on. The total work is on the order of

Σh ≥ 0 (n/2h+1) · h = (n/2) · Σh ≥ 0 h/2h = (n/2) · 2 = n

That is, bottom-up heap construction is O(n). This method is also called Floyd's method, after R. W. Floyd. A heap can also be built by inserting the elements one at a time and sifting each one up; that also yields a valid max-heap, but it takes O(n log n) in the worst case.

The cost of the sorting phase. The second loop runs n − 1 times, and in each round the root sifts down at most the height of the heap, that is, O(log n) steps. This phase is O(n log n) and determines the total time. Even in the worst case the time is O(n log n).

Memory and stability. Heap sort uses only a few variables; it works in place with O(1) extra memory. heapify is written with a loop, not recursion, so the call stack does not grow either. Heap sort is not stable: swapping the root with the last element can make an element jump over others with an equal key. It is not adaptive either; even a sorted input is first turned into a heap and still takes Θ(n log n).

Common mistake

Writing heapify(a, n, 0) in the second loop. If the heap size is not reduced, sifting counts the large elements already moved to the sorted region as children again and brings them back to the root. The sort breaks. The correct call is heapify(a, i, 0); the heap is only a[0..i−1].

3.8.6Code trace: building the heap

Here is the heap-building loop run on [3, 9, 2, 1, 4, 5], line by line. Here n = 6; the leaves are indices 3, 4, and 5. The loop starts at i = n/2 − 1 = 2.

for (int i = n / 2 - 1; i >= 0; i--)
  heapify(a, n, i);

void heapify(int[] a, int n, int i) {
  while (true) {
    int largest = i, left = 2 * i + 1, right = 2 * i + 2;
    if (left < n && a[left] > a[largest]) largest = left;
    if (right < n && a[right] > a[largest]) largest = right;
    if (largest == i) return;         // in place
    swap(a, i, largest);
    i = largest;                       // keep sinking
  }
}
Table 3.24: Trace of heap construction for a = [3, 9, 2, 1, 4, 5]. The numbers in parentheses are the values at those indices.
Call / roundCheckslargestActiona
heapify(6, 2)left = 5 (5) > 2: yes; right = 6 ≥ n5swap(2, 5)[3, 9, 5, 1, 4, 2]
↳ i = 5 (loop continues)left = 11 ≥ n5sifting ends[3, 9, 5, 1, 4, 2]
heapify(6, 1)left = 3 (1) > 9: no; right = 4 (4) > 9: no1no change[3, 9, 5, 1, 4, 2]
heapify(6, 0)left = 1 (9) > 3: yes; right = 2 (5) > 9: no1swap(0, 1)[9, 3, 5, 1, 4, 2]
↳ i = 1 (loop continues)left = 3 (1) > 3: no; right = 4 (4) > 3: yes4swap(1, 4)[9, 4, 5, 1, 3, 2]
↳ i = 4 (loop continues)left = 9 ≥ n4sifting ends[9, 4, 5, 1, 3, 2]

At i = 2, the only child of 2 is 5 (index 5); since 5 is larger, they are swapped and sifting continues at index 5. Index 5 is a leaf; sifting ends. At i = 1, 9 is larger than its children (1 and 4); nothing changes. At i = 0, 3 is swapped with its larger child 9 and sinks to index 1. There its children are 1 and 4; it is swapped with 4 and sinks to a leaf. The loop ends at i = −1. The result is [9, 4, 5, 1, 3, 2]: every parent is larger than its children, and the largest element, 9, is at the root.

Note that the check for right is made against a[largest], not against a[i]. In the i = 0 step, the right child 5 is larger than the node's own value 3 but smaller than the left child 9. The correct choice is the larger child, 9. Had the right child been compared with a[i], 5 would have been chosen; 5 would rise to the root with 9 left below it, and the heap condition would be broken.

3.9Linear-time sorting

Merge sort and heap sort are Θ(n log n) in the worst case. Is it possible to find a faster comparison sort? This section proves that the answer is no. It then presents three algorithms that sort in linear time by using the key values directly instead of comparing elements.

3.9.1The lower bound for comparison sorting

A comparison sort learns about the input only from the answers to questions of the form "is ai ≤ aj?" The behavior of such an algorithm can be shown with a decision tree. Each internal node of the tree is a comparison; the label i:j says that ai and aj are compared. The left branch follows the answer "≤" and the right branch the answer ">". Each leaf is the ordering the algorithm produces after that sequence of answers. Given an input, the algorithm follows a single path from the root to a leaf. The length of the path is the number of comparisons made on that input.

≤>≤>≤>≤>≤>1:22:31:3⟨1,2,3⟩1:3⟨2,1,3⟩2:3⟨1,3,2⟩⟨3,1,2⟩⟨2,3,1⟩⟨3,2,1⟩3! = 6 leaves → height ≥ ⌈log₂ 6⌉ = 3
Figure 3.26: The decision tree of insertion sort on three elements. Internal nodes are the comparisons i:j, and the leaves are the six permutations. For 3! = 6 leaves the height must be at least ⌈log2 6⌉ = 3.
Theorem 3.3 (Comparison lower bound)

Every comparison sort that sorts n distinct elements makes Ω(n log n) comparisons in the worst case.

Consider the decision tree of the algorithm. An input of distinct elements has n! possible orderings, and each is sorted by a different permutation. If the algorithm is correct, every permutation must appear in at least one leaf; the tree has at least n! leaves. A binary tree of height h can have at most 2h leaves. Hence 2h ≥ n!, that is, h ≥ log2(n!). Since each of the last n/2 factors of n! is at least n/2, we have n! ≥ (n/2)n/2. Taking logarithms gives log2(n!) ≥ (n/2) log2(n/2) = Ω(n log n). The height of the tree is the number of comparisons in the worst case. □

The theorem has two important consequences. First, merge sort and heap sort are asymptotically optimal comparison sorts; their worst cases equal the lower bound. Second, sorting faster requires information other than comparisons. If the keys are small integers, the values themselves can be used as array indices; counting sort and radix sort do this.

Example 3.5

What is the least number of comparisons that every algorithm sorting three distinct elements by comparison alone must make in the worst case?

The decision tree must have 3! = 6 leaves. Two comparisons can distinguish at most 22 = 4 outcomes, which is not enough for six permutations. Three comparisons can distinguish 23 = 8 ≥ 6 outcomes. The answer is ⌈log2 6⌉ = 3. Note that in the tree of Figure 3.26 some leaves are reached with two comparisons; the lower bound applies only to the longest path. For eight elements the bound is ⌈log2 40,320⌉ = 16; the worst case of 17 comparisons for merge sort is very close to it.

3.9.2Counting sort

Counting sort sorts elements whose keys are integers in a small range without comparing them at all. The input is the array A[1..n], and every key is in the set {1, 2, …, k}. The output is written to the array B[1..n]. A counter array C[1..k] is used as temporary storage.

The idea of the algorithm is this: if the number of elements with key less than or equal to i is known, then the output position of the last element with key i is known as well. For example, if five elements have a key less than or equal to 3, the last 3 is written to the fifth cell of the output. The algorithm consists of four loops:

for i = 1 to k
  C[i] = 0
for j = 1 to n
  C[A[j]] = C[A[j]] + 1   // C[i] = |{key = i}|
for i = 2 to k
  C[i] = C[i] + C[i−1]    // C[i] = |{key ≤ i}|
for j = n downto 1
  B[C[A[j]]] = A[j]
  C[A[j]] = C[A[j]] − 1
  1. The first loop zeroes all the counters.
  2. The second loop scans the input and counts how many times each key occurs. At the end, C[i] is the number of elements with key i.
  3. The third loop computes the prefix sums: each counter is added to the one on its left. At the end, C[i] is the number of elements with key less than or equal to i.
  4. The fourth loop scans the input from back to front. Each element is written to the cell B[C[A[j]]] and the counter is decremented; the next element with the same key falls one cell to the left.

3.9.3Step by step: A = [4, 1, 3, 4, 3]

The input is A = [4, 1, 3, 4, 3], n = 5, with keys in {1, …, 4} (k = 4). The arrays are 1-based.

Table 3.25: Trace of counting sort. The array C is written as [C[1], C[2], C[3], C[4]].
LoopStepActionCB
1—counters are zeroed[0, 0, 0, 0][–, –, –, –, –]
2j = 1A[1] = 4, C[4]++[0, 0, 0, 1]
2j = 2A[2] = 1, C[1]++[1, 0, 0, 1]
2j = 3A[3] = 3, C[3]++[1, 0, 1, 1]
2j = 4A[4] = 4, C[4]++[1, 0, 1, 2]
2j = 5A[5] = 3, C[3]++[1, 0, 2, 2]
3i = 2C[2] = 0 + 1[1, 1, 2, 2]
3i = 3C[3] = 2 + 1[1, 1, 3, 2]
3i = 4C[4] = 2 + 3[1, 1, 3, 5]
4j = 5A[5] = 3 → B[3][1, 1, 2, 5][–, –, 3, –, –]
4j = 4A[4] = 4 → B[5][1, 1, 2, 4][–, –, 3, –, 4]
4j = 3A[3] = 3 → B[2][1, 1, 1, 4][–, 3, 3, –, 4]
4j = 2A[2] = 1 → B[1][0, 1, 1, 4][1, 3, 3, –, 4]
4j = 1A[1] = 4 → B[4][0, 1, 1, 3][1, 3, 3, 4, 4]

After the counting loop, C = [1, 0, 2, 2]: there is one 1, two 3s, and two 4s; there is no 2. After the prefix sums, C = [1, 1, 3, 5]. These values are the last output position of each key: the last position of 1 is 1, of 3 is 3, and of 4 is 5. The final loop walks the input from right to left. A[5] = 3 is written to B[3] and C[3] drops to 2; the next 3 (A[3]) therefore falls into B[2]. The result is B = [1, 3, 3, 4, 4]. No comparison has been made.

A:4134312345C:11351234B:12345
Figure 3.27: The prefix sums are ready: C = [1, 1, 3, 5]. C[i] is the position in B of the last element with key i. B is still empty.

Walking the last loop from back to front gives stability. Of two elements with equal keys, the one that comes later in the input is processed first and written to the cell farther right; the earlier one lands to its left. The input order of equal elements is thus preserved in the output. Had the loop run from front to back, the order of equal elements would be reversed; the result would still be sorted, but the algorithm would be unstable.

3.9.4Complexity and Java code

Table 3.26: The cost of each loop of counting sort.
LoopWorkTime
1C[1..k] = 0Θ(k)
2countingΘ(n)
3prefix sumsΘ(k)
4placing into BΘ(n)
TotalΘ(n + k)

The total time is Θ(n + k). If the key range is k = O(n), the time is Θ(n). This does not contradict the comparison lower bound; counting sort makes no comparisons, so the assumption of the theorem does not apply to it. The extra memory is Θ(n + k): the output array and the counter array. If k is very large the algorithm is impractical. For 32-bit integers, for example, about 4.3 billion counters would be needed.

The Java version is 0-based and uses the range 0 … max, where max is the largest element of the array.

int[] countingSort(int[] a) { // values ≥ 0
  if (a.length == 0) return a;
  int max = Arrays.stream(a).max().getAsInt();
  int[] count = new int[max + 1];
  for (int x : a) count[x]++;
  for (int i = 1; i <= max; i++) count[i] += count[i - 1];
  int[] out = new int[a.length];
  for (int i = a.length - 1; i >= 0; i--) {
    out[count[a[i]] - 1] = a[i];
    count[a[i]]--;
  }
  return out;
}

The code is written for non-negative integers only; an empty array returns immediately, because a largest element exists only in a non-empty array. Unlike the pseudocode, the counters are zeroed automatically by new int[max + 1]. After the prefix sums, count[x] is the number of elements with key less than or equal to x; since the output is 0-based, the last position of x is count[x] − 1. For example, for A = [2, 5, 3, 0, 2, 3, 0, 3] the tallies are [2, 0, 2, 3, 0, 1] and the prefix sums are [2, 2, 4, 7, 7, 8]; the output is [0, 0, 2, 2, 3, 3, 3, 5].

Common mistake

Running the last loop from front to back. The output is still sorted, but elements with equal keys are written in reverse order. Used alone, counting sort may not show this difference; used as an intermediate step of radix sort, it destroys the order built by the earlier digits and makes the result wrong.

3.9.5Radix sort

Counting sort is very fast when the key range is small, but its memory need explodes as the range grows. Radix sort solves this problem by sorting large numbers digit by digit. Each digit takes only a value from 0 to 9, so one counting sort with k = 10 per pass is enough.

The version described here is LSD (least significant digit) radix sort: sorting starts from the least significant digit, the ones digit, and continues with the tens, the hundreds, and so on. In each pass a stable sort is made on that digit. Let d be the number of digits and b the base. Each pass takes Θ(n + b) and there are d passes; the total time is Θ(d · (n + b)). If d and b are constants, the time is Θ(n). The extra memory is Θ(n + b); the algorithm is not in place.

int[] radixSort(int[] a) { // values ≥ 0
  if (a.length == 0) return a;
  int max = Arrays.stream(a).max().getAsInt();
  for (long exp = 1; max / exp > 0; exp *= 10)
    a = countByDigit(a, (int) exp);
  return a;
}
int[] countByDigit(int[] a, int exp) {
  int n = a.length;
  int[] out = new int[n], count = new int[10];
  for (int x : a) count[(x / exp) % 10]++;
  for (int i = 1; i < 10; i++) count[i] += count[i - 1];
  for (int i = n - 1; i >= 0; i--) {
    int d = (a[i] / exp) % 10;
    out[--count[d]] = a[i];
  }
  return out;
}
  • radixSort grows the variable exp as 1, 10, 100, and so on. The condition max / exp > 0 holds as long as the largest number still has an unprocessed digit. For 802, exp takes the values 1, 10, and 100; at 1000, 802/1000 = 0 and the loop ends. exp is of type long: if max is 109 or larger, exp *= 10 on an int would overflow and the loop could continue wrongly. Like counting sort, the code is meant only for non-negative integers.
  • countByDigit is counting sort adapted to a single digit. The digit of a number is found with (x / exp) % 10: for 802 at exp = 10, 802/10 = 80 and 80 % 10 = 0.
  • The last loop again walks from back to front and ensures stability. The expression out[--count[d]] first decrements the counter and then uses the decremented value as the index; it does in one expression what count[x] − 1 does in the Java version of counting sort.
Example 3.6

Let the input be [170, 45, 75, 90, 802, 24, 2, 66]. The largest number, 802, has three digits, so three passes are made. Missing digits count as 0: 45 is 045 as a three-digit number.

  1. Ones digit (0, 5, 5, 0, 2, 4, 2, 6): [170, 90, 802, 2, 24, 45, 75, 66]. 170 and 90, whose ones digit is 0, kept their input order; so did 802 and 2, and 45 and 75.
  2. Tens digit: [802, 2, 24, 45, 66, 170, 75, 90]. 802 and 2, whose tens digit is 0, took their places in the order of the previous pass (802 first).
  3. Hundreds digit: [2, 24, 45, 66, 75, 90, 170, 802]. All digits have been processed and the array is sorted.
sorted by ones digit1700900802222244455755666
Figure 3.28: After the first pass the array is sorted by the ones digit. The underlined digits are the ones digits, used as the key in this pass.

3.9.6Why is stability needed?

The correctness of LSD radix sort rests on the following invariant: after pass k, the array is sorted by the last k digits of the numbers. The next pass sorts by digit (k + 1). Two numbers that differ in this digit come into the right order. For two numbers with the same digit, the earlier passes have determined the order, and that order is correct with respect to the last k digits. It is essential that this order be preserved, that is, that the sub-sort be stable.

input456167276467273123ones273123456276167467tens123456167467273276hundreds123167273276456467
Figure 3.29: Sorting 456, 167, 276, 467, 273, 123 in three passes. The green columns are the trailing digits that are sorted so far: after k passes the array is sorted by the last k digits.

In the example in the figure, after the first pass the array is [273, 123, 456, 276, 167, 467]. In the second pass 167 and 467 have equal tens digits (6). A stable sort keeps the order coming from the first pass: 167 comes first. This order is correct, since the ones digits of the two numbers are also equal (7) and the input order was preserved. In the last pass, 273 and 276 have equal hundreds digits (2). Had the sub-sort been unstable, these two could have traded places, and the result would be a wrong array such as [123, 167, 276, 273, …]. The result is [123, 167, 273, 276, 456, 467].

Radix sort can also start from the most significant digit; this version is called MSD (most significant digit). The MSD version first splits the numbers into buckets by the first digit and then sorts each bucket separately, recursively. It is widely used for sorting strings. The LSD version is simpler but requires all keys to be of the same length.

3.9.7Code trace: countByDigit()

int[] countByDigit(int[] a, int exp) {
  int n = a.length;
  int[] out = new int[n], count = new int[10];
  for (int x : a) count[(x / exp) % 10]++;
  for (int i = 1; i < 10; i++) count[i] += count[i - 1];
  for (int i = n - 1; i >= 0; i--) {
    int d = (a[i] / exp) % 10;
    out[--count[d]] = a[i];
  }
  return out;
}

Let us trace the call countByDigit(a, 1) on [32, 15, 41, 23, 11]. The ones digits are 2, 5, 1, 3, 1 in order.

Table 3.27: Trace of countByDigit([32, 15, 41, 23, 11], 1). count is shown only with cells 0–5; cells 6–9 are always 5.
StageActioncount[0..5]out
countingdigits 2, 5, 1, 3, 1[0, 2, 1, 1, 0, 1][–, –, –, –, –]
prefixprefix sums[0, 2, 3, 4, 4, 5][–, –, –, –, –]
i = 411, d = 1, --count[1] = 1[0, 1, 3, 4, 4, 5][–, 11, –, –, –]
i = 323, d = 3, --count[3] = 3[0, 1, 3, 3, 4, 5][–, 11, –, 23, –]
i = 241, d = 1, --count[1] = 0[0, 0, 3, 3, 4, 5][41, 11, –, 23, –]
i = 115, d = 5, --count[5] = 4[0, 0, 3, 3, 4, 4][41, 11, –, 23, 15]
i = 032, d = 2, --count[2] = 2[0, 0, 2, 3, 4, 4][41, 11, 32, 23, 15]

After the prefix sums, count[d] is the number of elements whose digit is less than or equal to d; for example, count[3] = 4. This number is one more than the position of the last element with that digit in out. Walking from right to left, 11 is processed first and written to out[1]. 41 and 11 have the same ones digit; 41 is processed later and falls into out[0], to the left of 11. In the input too, 41 came before 11: the order is preserved. The result is [41, 11, 32, 23, 15], sorted by the ones digit. The next pass (exp = 10) looks at the tens digit and produces [11, 15, 23, 32, 41]. 11 and 15 have equal tens digits; the order built by the first pass (11 first) is preserved.

3.9.8Bucket sort

Bucket sort reaches linear expected time by making an assumption about the distribution of the input. Suppose the input consists of real numbers uniformly distributed over the interval [0, 1). The algorithm opens n buckets and puts the value x into bucket number ⌊n · x⌋. Each bucket is sorted internally, for example with insertion sort. Then the buckets are concatenated in order.

A = .78, .17, .39, .26, .72, .94, .21, .12, .23, .680∅1.12.172.21.23.263.394∅5∅6.687.72.788∅9.94Concatenate: .12, .17, .21, .23, .26, .39, .68, .72, .78, .94
Figure 3.30: Bucket sort. Ten numbers (.78, .17, .39, .26, .72, .94, .21, .12, .23, .68) are distributed into ten buckets: for example, .78 falls into bucket ⌊10 · 0.78⌋ = 7. The buckets are sorted and concatenated in order.

In the example in the figure, three numbers (.21, .23, .26) fall into bucket 2, and two numbers each into buckets 1 and 7; buckets 0, 4, 5, and 8 are empty. If the distribution is uniform, on average one element falls into each bucket, and sorting the buckets takes Θ(n) expected time in total. Distributing and concatenating are also linear; the expected total time is Θ(n). But if the assumption fails, for instance if all elements fall into a single bucket, that bucket is sorted by insertion sort in Θ(n2). Bucket sort is stable if the buckets are sorted with a stable algorithm, and it needs Θ(n) extra memory.

3.10Timsort

The sorting algorithms used in libraries differ somewhat from the pure algorithms of textbooks. They exploit patterns common in real data and combine several algorithms. Timsort is the best-known example.

3.10.1A hybrid algorithm

Timsort is a hybrid sorting algorithm that Tim Peters designed for Python in 2002. Today Java uses Timsort for object arrays (Arrays.sort(Object[]), List.sort), and so does Python's sorted. The starting point of the algorithm is the observation that real data is often not completely random. It contains long stretches that are already sorted. A few records appended to a table, a partly sorted log file, or two sorted lists concatenated are examples.

Timsort uses these sorted stretches, called runs. First the array is scanned from left to right and natural runs are found; a descending run is reversed to make it ascending. Very short runs are extended with insertion sort up to a minimum length (minrun, in practice between 32 and 64). Since insertion sort is very fast on small and nearly sorted pieces, this choice is sound. Then the runs are merged in pairs with the merge step of merge sort. If many elements in a row are taken from one run during a merge, the algorithm switches to "galloping" mode. In this mode the position of the next element is found by exponential search, and a whole block of elements is copied at once.

Timsort is stable, because both insertion sort and merging are stable. In the worst case it is O(n log n). If the input is already sorted, a single run is found and the algorithm finishes with n − 1 comparisons, that is, in Θ(n). It uses at most O(n) extra memory for merging. Because stability matters when sorting objects, Java uses quicksort for primitive types and Timsort for objects.

The following code is a simplified version of Timsort: it does not look for natural runs but splits the array into fixed-length pieces. It sorts the pieces with insertionSort(a, lo, hi) and then merges them with the merge method from 3.6.4.

static final int MIN_RUN = 4;
void timSort(int[] a) {
  int n = a.length;
  for (int i = 0; i < n; i += MIN_RUN)            // 1) runs
    insertionSort(a, i, Math.min(i + MIN_RUN - 1, n - 1));
  for (int size = MIN_RUN; size < n; size *= 2)  // 2) merge
    for (int lo = 0; lo < n; lo += 2 * size) {
      int mid = lo + size - 1;
      int hi = Math.min(lo + 2 * size - 1, n - 1);
      if (mid < hi) merge(a, lo, mid, hi);
    }
}
  • The first loop divides the array into pieces of length MIN_RUN and sorts each with insertion sort. The last piece may be shorter; Math.min(i + MIN_RUN - 1, n - 1) keeps the index from leaving the array.
  • The second loop does the merging from the bottom up. size is the length of the sorted pieces to be merged and doubles in each round. In each round, two adjacent pieces [lo..mid] and [mid+1..hi] are merged.
  • If mid < hi does not hold, there is no piece on the right to merge with; the single remaining piece is left as it is in this round.

This loop structure is a non-recursive, "bottom-up" version of merge sort. It uses no recursion stack.

3.10.2Step by step

Let us trace the simplified Timsort with MIN_RUN = 4 on the array [5, 21, 7, 23, 19, 10, 3, 12, 8, 1] (n = 10).

Table 3.28: The steps of the simplified Timsort.
StepActionArray
Run [0..3]insertion: [5, 21, 7, 23] → [5, 7, 21, 23][5, 7, 21, 23, 19, 10, 3, 12, 8, 1]
Run [4..7]insertion: [19, 10, 3, 12] → [3, 10, 12, 19][5, 7, 21, 23, 3, 10, 12, 19, 8, 1]
Run [8..9]insertion: [8, 1] → [1, 8][5, 7, 21, 23, 3, 10, 12, 19, 1, 8]
size = 4[0..3] + [4..7] are merged[3, 5, 7, 10, 12, 19, 21, 23, 1, 8]
size = 4lo = 8: mid = 11 ≥ hi = 9, no partnerunchanged
size = 8[0..7] + [8..9] are merged[1, 3, 5, 7, 8, 10, 12, 19, 21, 23]

The array is first divided into three runs; the last run has two elements. Each run is sorted with insertion sort. In the size = 4 round the first two runs merge. The third run has no partner to merge with, because mid = 8 + 4 − 1 = 11 goes past the end of the array (hi = 9). In the size = 8 round the eight-element piece and the two-element piece merge and the array is sorted. When size = 16 ≥ n, the loop ends.

size = 4: merge(0, 3, 7)3051721031241952162371889
Figure 3.31: After merge(0, 3, 7) in the size = 4 round. The first eight cells are sorted (green); the run [1, 8] in the last two cells awaits the next round.

3.11Comparing the algorithms

We can now set the chapter's algorithms side by side. This section first collects the asymptotic properties in a table, then gives actual comparison counts, and discusses which algorithm to choose in which situation.

3.11.1Complexity table

Table 3.29: Comparison of the sorting algorithms. (*) recursion stack, if the smaller part is processed first. (†) expected under a uniform distribution. k: key range, d: number of digits, b: base. The Θ(n) best case of Timsort applies to the real version, which looks for natural runs.
AlgorithmBestAverageWorstExtra memoryStableIn place
Bubble (with flag)Θ(n)Θ(n²)Θ(n²)O(1)YesYes
InsertionΘ(n)Θ(n²)Θ(n²)O(1)YesYes
SelectionΘ(n²)Θ(n²)Θ(n²)O(1)NoYes
Shell (n/2 gaps)Θ(n log n)depends on gapsΘ(n²)O(1)NoYes
MergeΘ(n log n)Θ(n log n)Θ(n log n)Θ(n)YesNo
QuicksortΘ(n log n)Θ(n log n)Θ(n²)O(log n)*NoYes
Heap sortO(n log n)Θ(n log n)Θ(n log n)O(1)NoYes
CountingΘ(n + k)Θ(n + k)Θ(n + k)Θ(n + k)YesNo
Radix (LSD)Θ(d(n + b))Θ(d(n + b))Θ(d(n + b))Θ(n + b)YesNo
BucketΘ(n)Θ(n)†Θ(n²)Θ(n)YesNo
TimsortΘ(n)Θ(n log n)Θ(n log n)O(n)YesNo

Two details in the table call for explanation. The best case of heap sort is written with O, not Θ: if all keys are equal, no sift goes anywhere and the algorithm finishes in linear time. With distinct keys the best case is also Θ(n log n). The extra memory of quicksort is only the recursion stack; if the larger part is handled with a loop and the smaller with recursion, the stack depth does not exceed O(log n).

3.11.2Measurements: n = 1000

Asymptotic notation hides constant factors. To see actual behavior, the code in this chapter was run on three kinds of input with n = 1000 elements, and the element comparisons were counted. The random array was generated with a fixed seed.

Table 3.30: Element comparison counts for n = 1000. For reference, n2/2 ≈ 500,000 and n log2 n ≈ 9,966.
AlgorithmRandomSortedReverse sorted
Bubble (with flag)497,960999499,500
Insertion252,205999499,500
Selection499,500499,500499,500
Shell (n/2)14,7238,00611,716
Merge8,6935,0444,932
Quicksort (last element as pivot)11,384499,500499,500
Heap sort16,79117,58315,965

The table confirms the theory with numbers. Selection sort makes exactly n(n − 1)/2 = 499,500 comparisons on all three inputs. Bubble sort and insertion sort finish with only n − 1 = 999 comparisons on the sorted input. On the random input the count for insertion sort is about n2/4 = 250,000, and for bubble sort about n2/2. Merge sort stays below n log2 n on every input. On sorted and reverse-sorted inputs it makes about half as many comparisons, because one of the arrays being merged always ends early. Quicksort is a little above merge sort on the random input and close to the exact expected value in 3.7.8 (about 10,986). But on sorted and reverse-sorted inputs the version that takes the last element as pivot falls into its worst case and makes as many comparisons as selection sort. Heap sort is almost independent of the input; since it is not adaptive, it spends 17,583 comparisons even on the sorted input.

The comparison count is not the only criterion. Quicksort, although it makes more comparisons than merge sort, is usually faster in practice. The reason is that it does not copy to auxiliary arrays and it walks through memory sequentially. Heap sort, besides its comparison count, jumps around in memory (from index i to 2i + 1), uses the cache badly, and is often slower than quicksort.

3.11.3Which algorithm when?

Small or nearly sorted array
Insertion sort: low overhead, adaptive, and stable. Since its time is Θ(n + I), it is also fast on large arrays with few inversions.
General purpose, speed first
Quicksort, with a random pivot or median of three. It is cache-friendly and in place.
Stability required
Merge sort or Timsort. This is why the object sort in libraries is Timsort.
Worst-case guarantee and little memory
Heap sort: O(n log n) and O(1) extra memory. A hybrid algorithm called introsort starts with quicksort and switches to heap sort if the recursion gets too deep, thereby holding the worst case to O(n log n).
Small integer keys
Counting sort or radix sort: Θ(n + k) and Θ(d(n + b)).
Linked list or external memory
Merge sort. It needs no random access; it reads elements sequentially and writes them sequentially. A large file that does not fit in memory is sorted piece by piece and the pieces are merged. A linked list can also be merged without an extra array, simply by changing links.

Bubble sort and selection sort are mostly for teaching. Selection sort makes sense only where writing is very expensive, since it makes at most n − 1 swaps.

3.12Common mistakes

Most errors in sorting code cluster around boundary indices, temporary variables, and equality conditions. The list below brings together the mistakes described throughout the chapter.

Table 3.31: Common mistakes in sorting code.
MistakeConsequenceCorrect form
Running past the array boundWriting j < n in bubble sort makes a[j+1] fall outside the array.j < n - 1 - i
Not saving the keyIn insertion sort the first shift overwrites the element being inserted.key = a[i] before the loop
Keeping the minimum as a valueIn selection sort the cell to swap is unknown.Keep the index min
Breaking stability< in the merge, or walking counting sort front to back, reverses the order of equal elements.L[i] <= R[j]; walk back to front
Including the pivot in the recursionquickSort(a, lo, p) may fail to shrink the part; infinite recursion.lo..p − 1 and p + 1..hi
"Quicksort is always n log n"On a sorted input a fixed pivot gives Θ(n2) and recursion of depth n.Random pivot or median of three
Not shrinking the heap sizeElements moved to the end mix back into the heap.heapify(a, i, 0)

What these mistakes have in common is that most are spotted at once when traced by hand on a small example. Good test inputs are: the shortest arrays (one and two elements) for boundary errors, records with equal keys for stability errors, and a sorted array for the bad case of quicksort.

3.13Summary

  • Sorting means finding a permutation that puts the elements of an array in ascending (or descending) order by key. Algorithms are compared by time (best, average, worst), extra memory, stability, in-place operation, adaptivity, and whether they are online.
  • A stable algorithm preserves the relative order of records with equal keys; multi-key sorting and radix sort rely on this. Bubble, insertion, merge, counting, radix, and Timsort are stable; selection, Shell, quicksort, and heap sort are unstable.
  • An inversion is a pair of elements in the wrong order relative to each other. An adjacent swap removes exactly one inversion; the number of swaps in bubble sort and the number of shifts in insertion sort equal the number of inversions. A reverse-sorted array has n(n − 1)/2 inversions.
  • Bubble sort swaps neighbors; in each pass the largest of the remaining elements goes to the end. The version with a flag is Θ(n) in the best case and Θ(n2) otherwise.
  • Insertion sort saves the key, shifts the larger elements, and places the key. Its time is Θ(n + I); it is the best choice for small and nearly sorted arrays.
  • Selection sort moves the minimum to the front in each round: n(n − 1)/2 comparisons on every input, at most n − 1 swaps.
  • Shell sort performs insertion sort with decreasing gaps; its time depends on the gap sequence (worst case Θ(n2) with n/2 gaps, O(n1.5) with Hibbard's sequence).
  • Merge sort follows the steps divide, sort, merge: T(n) = 2T(n/2) + Θ(n) = Θ(n log n) on every input. It needs Θ(n) extra memory and is stable.
  • Quicksort partitions around a pivot; the pivot settles in its final place and no merging is needed. It is Θ(n log n) on average and Θ(n2) in the worst case. With a random pivot, Θ(n2) occurs only with very small probability; median of three prevents the bad case on sorted and reverse-sorted inputs but not on specially constructed ones.
  • Heap sort turns the array into a max-heap in O(n), then moves the root to the end and sifts n − 1 times: O(n log n) in the worst case, O(1) extra memory.
  • Every comparison sort makes Ω(n log n) comparisons in the worst case (the decision tree has n! leaves). Counting sort takes Θ(n + k), radix sort Θ(d(n + b)), and bucket sort an expected Θ(n) under a uniform distribution; since they make no comparisons, they are not bound by this limit.
  • Timsort is a stable hybrid algorithm that extends sorted runs with insertion sort and combines them by merging; it is the object sort of Java and Python.

3.14Key terms

  • sorting
  • swap
  • in-place
  • stable (sort)
  • adaptive (sort)
  • inversion
  • bubble sort
  • insertion sort
  • selection sort
  • Shell sort
  • divide and conquer
  • merge
  • merge sort
  • recurrence (relation)
  • recursion tree
  • master theorem
  • quicksort
  • pivot
  • partition
  • median of three
  • heap
  • heap sort
  • comparison sort lower bound
  • lower bound
  • counting sort
  • radix sort
  • LSD / MSD radix sort
  • bucket sort
  • Timsort
  • quadratic
  • linearithmic
  • best / average / worst case

3.15Test Yourself

  1. How many comparisons and how many shifts does insertion sort make while sorting [2, 4, 1, 3]?

    Answer

    i = 1: 2 > 4 is false; 1 comparison, no shift. i = 2 (1): 4 and 2 shift, the scan stops at j = −1; 2 comparisons, 2 shifts. i = 3 (3): 4 shifts, 2 > 3 is false; 2 comparisons, 1 shift. In total 5 comparisons and 3 shifts. The inversions are (2, 1), (4, 1), (4, 3); their number equals the number of shifts.

  2. How many passes, comparisons, and swaps does bubble sort with a flag make on [2, 3, 4, 5, 1]? Why is the result bad even though the array is nearly sorted?

    Answer

    In each pass the 1 moves only one cell left: [2, 3, 4, 1, 5], [2, 3, 1, 4, 5], [2, 1, 3, 4, 5], [1, 2, 3, 4, 5]. A swap occurs in all four passes, so the flag never allows an early exit. There are 4 + 3 + 2 + 1 = 10 comparisons and 4 swaps. Because a small element at the end can advance only one cell per pass through adjacent swaps, bubble sort reaches its worst-case comparison count on this input. Insertion sort sorts the same array with 3 + 4 = 7 comparisons.

  3. Let the records be (4, a), (2, b), (4, c), (1, d), sorted by the number only. Does selection sort break stability on this input?

    Answer

    Yes. In the first round the minimum, (1, d), is swapped with the (4, a) at the front: (1, d), (2, b), (4, c), (4, a). In the second round (2, b) is in place. In the third round no swap happens, because (4, a) is not strictly smaller. In the end (4, c) is in front of (4, a); in the input a came first.

  4. partition(a, 0, 4) (Lomuto, last element as pivot) runs on [3, 7, 1, 6, 4]. What does the method return and what does the array become?

    Answer

    The pivot is 4, i = −1. j = 0: 3 ≤ 4, i = 0, swap with itself. j = 1: 7 is larger. j = 2: 1 ≤ 4, i = 1, 7 and 1 trade places: [3, 1, 7, 6, 4]. j = 3: 6 is larger. The final swap a[2] ↔ a[4] gives [3, 1, 4, 6, 7]. The method returns 2; the pivot 4 is in its final place at index 2.

  5. What is the max-heap built bottom-up from [1, 2, 3, 4, 5, 6, 7]?

    Answer

    i = 2: 3 is swapped with its larger child 7: [1, 2, 7, 4, 5, 6, 3]. i = 1: 2 with its larger child 5: [1, 5, 7, 4, 2, 6, 3]. i = 0: 1 is swapped with its larger child 7 and sinks to index 2; there its children are 6 and 3, and it is swapped with 6. The result is [7, 5, 6, 4, 2, 1, 3]. Even a sorted array takes quite a few swaps to build a heap; heap sort is not adaptive.

  6. What is the maximum number of comparisons merge sort needs to sort a 16-element array in the worst case? What is the comparison lower bound?

    Answer

    There are four levels of merging: eight merges of 2 elements, four of 4 elements, two of 8 elements, and one of 16 elements. 8 · 1 + 4 · 3 + 2 · 7 + 1 · 15 = 49. The lower bound is ⌈log2 16!⌉ = ⌈44.25⌉ = 45; merge sort is close to this bound.

  7. The Java method countingSort is called with [1, 0, 2, 1, 0]. What is the count array after the counting loop and the prefix sums?

    Answer

    max = 2, so the counter has three cells. The tallies are [2, 2, 1]; the prefix sums become [2, 4, 5]. The last loop walks from right to left and the output is [0, 0, 1, 1, 2]. No comparisons are made; the time is Θ(n + k).

  8. The array [53, 21, 33, 12] is sorted with LSD radix sort. What is the array after the first pass? Why is the order of 53 and 33 preserved?

    Answer

    The ones digits are 3, 1, 3, 2; a stable sort gives [21, 12, 53, 33]. The ones digits of 53 and 33 are equal, and because 53 came first in the input it stays first. The second pass produces [12, 21, 33, 53] by the tens digit.

  9. In an array of a million elements only ten elements are out of place, each at most a few cells from its correct position. Which algorithm should be chosen for a fast, stable sort?

    Answer

    Insertion sort or Timsort. The number of inversions I is very small; the time of insertion sort is Θ(n + I), that is, linear. Timsort also finds the long sorted runs and finishes in nearly linear time. Merge sort would still spend Θ(n log n); selection sort is Θ(n2).

3.16Further reading

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms (4th ed., 2022), Chapters 2, 6, 7, and 8: insertion sort and merge sort with loop invariants, heap sort, the probabilistic analysis of quicksort, and linear-time sorting, all with proofs.
  • R. Sedgewick and K. Wayne, Algorithms (4th ed., 2011), Chapter 2: the same algorithms in Java code; its sections that measure comparison counts experimentally are an extended version of the measurement table in these notes.
  • D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed., 1998), Section 5.2: the most detailed treatment of the gap sequences of Shell sort and of the exact comparison counts of sorting algorithms.
  • T. Peters, "listsort.txt" (CPython source code): explains Timsort's run detection, minrun selection, and galloping mode in its designer's own words.

3.17References

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
  2. E. D. Demaine, C. E. Leiserson, MIT 6.046J Introduction to Algorithms lecture notes, 2005.
  3. C. A. R. Hoare, "Quicksort", The Computer Journal 5(1), 1962.
  4. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998.
  5. T. Peters, "listsort.txt" (Timsort design note), CPython, 2002.
  6. R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.
  7. D. L. Shell, "A High-Speed Sorting Procedure", Communications of the ACM 2(7), 1959.

Related pages: Chapter 3 slides · © Sercan Külcü. All rights reserved.