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.
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.
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.
| Algorithm | Central idea |
|---|---|
| Bubble sort | Compares neighbors and swaps them if they are out of order. |
| Insertion sort | Inserts the next element into its proper place in the sorted part. |
| Selection sort | Finds the smallest element, puts it first, then sorts the rest the same way. |
| Shell sort | Insertion-sorts distant elements first, with gaps that shrink step by step. |
| Merge sort | Splits the array in half, sorts the halves, then merges them. |
| Quicksort | Partitions around a pivot and sorts the two parts recursively. |
| Heap sort | Builds a max-heap and repeatedly moves the largest element to the end. |
| Counting / radix sort | No comparisons; counts the keys or distributes them digit by digit. |
| Timsort | A 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
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.
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.
- 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.
- 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).
- Round 3. The smallest is (2, D), swapped with (3, C): (1, B), (1, E), (2, D), (3, C), (3, A), (3, F).
- 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).
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.
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].
| Pass | j | Comparison | Result | Array |
|---|---|---|---|---|
| 1 | 0 | 3 > 1? | yes, swap | [1, 3, 5, 2, 6, 4] |
| 1 | 1 | 3 > 5? | no | [1, 3, 5, 2, 6, 4] |
| 1 | 2 | 5 > 2? | yes, swap | [1, 3, 2, 5, 6, 4] |
| 1 | 3 | 5 > 6? | no | [1, 3, 2, 5, 6, 4] |
| 1 | 4 | 6 > 4? | yes, swap | [1, 3, 2, 5, 4, 6] |
| 2 | 0 | 1 > 3? | no | [1, 3, 2, 5, 4, 6] |
| 2 | 1 | 3 > 2? | yes, swap | [1, 2, 3, 5, 4, 6] |
| 2 | 2 | 3 > 5? | no | [1, 2, 3, 5, 4, 6] |
| 2 | 3 | 5 > 4? | yes, swap | [1, 2, 3, 4, 5, 6] |
| 3 | 0 | 1 > 2? | no | [1, 2, 3, 4, 5, 6] |
| 3 | 1 | 2 > 3? | no | [1, 2, 3, 4, 5, 6] |
| 3 | 2 | 3 > 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.
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
swappedflag is set tofalse. If any swap happens during the pass, it becomestrue. - The inner loop (
j) walks over the neighboring pairs in the unsorted part. The lastielements were placed in earlier passes, so the condition isj < n - 1 - i. The final value ofjisn - 2 - i; thena[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 intemp, the right value is written to the left, and the saved value is written to the right. Withouttemp, the first assignment would destroy the left value. - If the flag is still
falsewhen a pass ends, no swap occurred in that pass, andbreakleaves 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.
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.
i | j | a[j] > a[j+1] | swapped | a |
|---|---|---|---|---|
| 0 | — | start of pass | false | [5, 1, 9, 2, 10] |
| 0 | 0 | 5 > 1: yes, swap | true | [1, 5, 9, 2, 10] |
| 0 | 1 | 5 > 9: no | true | [1, 5, 9, 2, 10] |
| 0 | 2 | 9 > 2: yes, swap | true | [1, 5, 2, 9, 10] |
| 0 | 3 | 9 > 10: no | true | [1, 5, 2, 9, 10] |
| 1 | — | start of pass | false | [1, 5, 2, 9, 10] |
| 1 | 0 | 1 > 5: no | false | [1, 5, 2, 9, 10] |
| 1 | 1 | 5 > 2: yes, swap | true | [1, 2, 5, 9, 10] |
| 1 | 2 | 5 > 9: no | true | [1, 2, 5, 9, 10] |
| 2 | — | start of pass | false | [1, 2, 5, 9, 10] |
| 2 | 0 | 1 > 2: no | false | [1, 2, 5, 9, 10] |
| 2 | 1 | 2 > 5: no | false | [1, 2, 5, 9, 10] |
| 2 | — | flag false → break | false | [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.
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.
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.
| Case | Input | Comparisons | Swaps | Time |
|---|---|---|---|---|
| Best | sorted | n − 1 (one pass) | 0 | Θ(n) |
| Average | random | ≈ n2/2 | ≈ n2/4 | Θ(n2) |
| Worst | reverse sorted | n(n − 1)/2 | n(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.
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:
- 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].
- Pass 2 (4 comparisons): 5 ↔ 1 and 5 ↔ 3; 2 swaps. The array is [2, 4, 1, 3, 5, 6].
- Pass 3 (3 comparisons): 4 ↔ 1 and 4 ↔ 3; 2 swaps. The array is [2, 1, 3, 4, 5, 6].
- Pass 4 (2 comparisons): 2 ↔ 1; 1 swap. The array is [1, 2, 3, 4, 5, 6].
- 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.
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.
i | key | Elements shifted right | Insertion index | Shifts | Array |
|---|---|---|---|---|---|
| 1 | 1 | 3 | 0 | 1 | [1, 3, 5, 2, 6, 4] |
| 2 | 5 | — | 2 | 0 | [1, 3, 5, 2, 6, 4] |
| 3 | 2 | 5, 3 | 1 | 2 | [1, 2, 3, 5, 6, 4] |
| 4 | 6 | — | 4 | 0 | [1, 2, 3, 5, 6, 4] |
| 5 | 4 | 6, 5 | 3 | 2 | [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 = 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 = 1because the one-elementa[0..0]is already sorted. keyis the element being inserted. The shifts will overwrite its cell, so it is saved first.jstarts 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, thewhileloop shifts it one cell right and decrementsj. The checkj >= 0in the condition keeps the scan from running past the start of the array. In Java,&&short-circuits: whenj = -1, the second condition is never evaluated anda[-1]is never read. - When the loop ends, either
j = -1ora[j] <= key. In both cases the vacated slot isj + 1, andkeyis 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.
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.
i | key | j | while condition | Action | a |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 ≥ 0 and 5 > 1: true | a[1] = 5, j = −1 | [5, 5, 9, 2, 10] |
| 1 | 1 | −1 | −1 ≥ 0: false | a[0] = 1 | [1, 5, 9, 2, 10] |
| 2 | 9 | 1 | 5 > 9: false | a[2] = 9 | [1, 5, 9, 2, 10] |
| 3 | 2 | 2 | 9 > 2: true | a[3] = 9, j = 1 | [1, 5, 9, 9, 10] |
| 3 | 2 | 1 | 5 > 2: true | a[2] = 5, j = 0 | [1, 5, 5, 9, 10] |
| 3 | 2 | 0 | 1 > 2: false | a[1] = 2 | [1, 2, 5, 9, 10] |
| 4 | 10 | 3 | 9 > 10: false | a[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.
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.
| Case | Input | Comparisons | Shifts | Time |
|---|---|---|---|---|
| Best | sorted | n − 1 | 0 | Θ(n) |
| Average | random | ≈ n2/4 | ≈ n2/4 | Θ(n2) |
| Worst | reverse sorted | n(n − 1)/2 | n(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).
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?
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].i = 2,key = 4: 5 > 4, shift; 2 > 4 is false. 2 comparisons, 1 shift. The array is [2, 4, 5, 6, 1, 3].i = 3,key = 6: 5 > 6 is false. 1 comparison, 0 shifts.i = 4,key = 1: 6, 5, 4, 2 shift;j = −1. 4 comparisons, 4 shifts. The array is [1, 2, 4, 5, 6, 3].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:
- It finds the smallest element of the unsorted part.
- It swaps that element with the first element of the unsorted part.
- 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.
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.
| Round | Initial minimum | Scanned | Minimum found | Swap | Array |
|---|---|---|---|---|---|
| 1 | 3 | 1, 5, 2, 6, 4 | 1 | 3 ↔ 1 | [1, 3, 5, 2, 6, 4] |
| 2 | 3 | 5, 2, 6, 4 | 2 | 3 ↔ 2 | [1, 2, 5, 3, 6, 4] |
| 3 | 5 | 3, 6, 4 | 3 | 5 ↔ 3 | [1, 2, 3, 5, 6, 4] |
| 4 | 5 | 6, 4 | 4 | 5 ↔ 4 | [1, 2, 3, 4, 6, 5] |
| 5 | 6 | 5 | 5 | 6 ↔ 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.
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 = 0ton - 2;iis the start of the unsorted part and the cell to be filled in this round. minholds 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 asa[min].- The inner loop scans the whole unsorted part, from
j = i + 1to 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]anda[i]are exchanged with three assignments. Ifmin == 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.
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]
i | j | a[j] < a[min] | min | a at end of round |
|---|---|---|---|---|
| 0 | 1 | 1 < 5: yes | 1 | |
| 0 | 2 | 10 < 1: no | 1 | |
| 0 | 3 | 2 < 1: no | 1 | |
| 0 | 4 | 9 < 1: no | 1 | a[1] ↔ a[0]: [1, 5, 10, 2, 9] |
| 1 | 2 | 10 < 5: no | 1 | |
| 1 | 3 | 2 < 5: yes | 3 | |
| 1 | 4 | 9 < 2: no | 3 | a[3] ↔ a[1]: [1, 2, 10, 5, 9] |
| 2 | 3 | 5 < 10: yes | 3 | |
| 2 | 4 | 9 < 5: no | 3 | a[3] ↔ a[2]: [1, 2, 5, 10, 9] |
| 3 | 4 | 9 < 10: yes | 4 | a[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.
| Measure | Value |
|---|---|
| Comparisons | n(n − 1)/2, on every input |
| Swaps | at most n − 1 |
| Time | best = average = worst = Θ(n2) |
| Extra memory | O(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.
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.
| Algorithm | Kind of move | [3, 1, 5, 2, 6, 4] | sorted 1…6 | reversed 6…1 |
|---|---|---|---|---|
| Bubble (with flag) | swap | 12 / 5 | 5 / 0 | 15 / 15 |
| Insertion | shift | 9 / 5 | 5 / 0 | 15 / 15 |
| Selection | swap | 15 / 5 | 15 / 0 | 15 / 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 / 2and 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 = gapto the end of the array. Eachiis the element to be inserted in its own group. The groups are processed interleaved, not one at a time: wheniincreases by one, the next element belongs to a different group. - The inner loop is the same as the
whileloop of insertion sort, except that the step isgapinstead of 1. It stops whenjfalls belowgapor when the group element on the left is not larger thankey.keyis written to the vacated cella[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.
gap | Groups (before) | Groups (after) | Shifts | Array |
|---|---|---|---|---|
| 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.
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.
gap | i | key | Inner loop | a |
|---|---|---|---|---|
| 3 | 3 | 1 | a[0] = 5 > 1: 5 shifts to index 3; stops at j = 0 | [1, 2, 6, 5, 4, 3] |
| 3 | 4 | 4 | a[1] = 2 ≤ 4: no shift | [1, 2, 6, 5, 4, 3] |
| 3 | 5 | 3 | a[2] = 6 > 3: 6 shifts to index 5; stops at j = 2 | [1, 2, 3, 5, 4, 6] |
| 1 | 1 | 2 | a[0] = 1 ≤ 2: no shift | [1, 2, 3, 5, 4, 6] |
| 1 | 2 | 3 | a[1] = 2 ≤ 3: no shift | [1, 2, 3, 5, 4, 6] |
| 1 | 3 | 5 | a[2] = 3 ≤ 5: no shift | [1, 2, 3, 5, 4, 6] |
| 1 | 4 | 4 | a[3] = 5 > 4: 5 shifts to index 4; stops at a[2] = 3 ≤ 4 | [1, 2, 3, 4, 5, 6] |
| 1 | 5 | 6 | a[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".
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.
- Divide: The problem is split into smaller subproblems.
- 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.
- 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.
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.
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.
| Order | Range | Left + right | Result | Comparisons |
|---|---|---|---|---|
| 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].
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 < hidoes 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 sumlo + hican exceed theintlimit (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; thenmergeis 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
LandRwithArrays.copyOfRange. The copy is necessary because the result is written directly into the same cells ofA, and without a copy it would overwrite elements not yet read. The upper bound ofcopyOfRangeis exclusive, which is whyq + 1andr + 1are written. iandjpoint to the next element ofLandRrespectively, andkto the cell ofAto be written.- The first
whilecompares the fronts as long as both arrays have elements; it writes the smaller or equal one toA[k]and advances the corresponding index. The expressionA[k++] = L[i++]first writes, then increments both indices. - When one array runs out, only one of the remaining two
whileloops 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.
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].
| Step | i, j, k | Comparison | Written | A[0..k] |
|---|---|---|---|---|
| 1 | 0, 0, 0 | L[0] = 1 ≤ R[0] = 2 | A[0] = 1 | [1] |
| 2 | 1, 0, 1 | L[1] = 3 > R[0] = 2 | A[1] = 2 | [1, 2] |
| 3 | 1, 1, 2 | L[1] = 3 ≤ R[1] = 4 | A[2] = 3 | [1, 2, 3] |
| 4 | 2, 1, 3 | L[2] = 5 > R[1] = 4 | A[3] = 4 | [1, 2, 3, 4] |
| 5 | 2, 2, 4 | L[2] = 5 ≤ R[2] = 7 | A[4] = 5 | [1, …, 5] |
| 6 | 3, 2, 5 | L[3] = 6 ≤ R[2] = 7 | A[5] = 6 | [1, …, 6] |
| 7 | 4, 2, 6 | L is exhausted; the rest of R is copied | A[6] = 7 | [1, …, 7] |
| 8 | 4, 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.
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.
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.
What is the maximum number of comparisons merge sort needs to sort an 8-element array?
- 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.
- 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.
- 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:
- A pivot element is chosen from the array. Call the pivot x.
- 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.
- The two parts are sorted 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 pivotThe 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 andA[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 i3.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.
j | A[j] | A[j] ≤ 6? | i | Array |
|---|---|---|---|---|
| 1 | 10 | no | 0 | [6, 10, 13, 5, 8, 3, 2, 11] |
| 2 | 13 | no | 0 | [6, 10, 13, 5, 8, 3, 2, 11] |
| 3 | 5 | yes: A[1] ↔ A[3] | 1 | [6, 5, 13, 10, 8, 3, 2, 11] |
| 4 | 8 | no | 1 | [6, 5, 13, 10, 8, 3, 2, 11] |
| 5 | 3 | yes: A[2] ↔ A[5] | 2 | [6, 5, 3, 10, 8, 13, 2, 11] |
| 6 | 2 | yes: A[3] ↔ A[6] | 3 | [6, 5, 3, 2, 8, 13, 10, 11] |
| 7 | 11 | no | 3 | [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 = 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.
j | a[j] ≤ 4? | i | Action | a |
|---|---|---|---|---|
| 0 | 2: yes | 0 | swap(0, 0) (with itself) | [2, 8, 7, 1, 3, 5, 6, 4] |
| 1 | 8: no | 0 | — | [2, 8, 7, 1, 3, 5, 6, 4] |
| 2 | 7: no | 0 | — | [2, 8, 7, 1, 3, 5, 6, 4] |
| 3 | 1: yes | 1 | swap(1, 3) | [2, 1, 7, 8, 3, 5, 6, 4] |
| 4 | 3: yes | 2 | swap(2, 4) | [2, 1, 3, 8, 7, 5, 6, 4] |
| 5 | 5: no | 2 | — | [2, 1, 3, 8, 7, 5, 6, 4] |
| 6 | 6: no | 2 | — | [2, 1, 3, 8, 7, 5, 6, 4] |
| last | — | 2 | swap(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);
}
}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.
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.
| Depth | Range | Piece | Pivot → index | Next 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.
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.
| Call | Status | Pivot → p | a (after the call) |
|---|---|---|---|
(0, 5) | lo < hi | 3 → 2 | [2, 1, 3, 5, 9, 8] |
(0, 1) | lo < hi | 1 → 0 | [1, 2, 3, 5, 9, 8] |
(0, −1) | empty part, base case | — | unchanged |
(1, 1) | one element, base case | — | unchanged |
(3, 5) | lo < hi | 8 → 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].
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.
| Case | When? | Recurrence | Time |
|---|---|---|---|
| Best | pivot is the median every time | T(n) = 2T(n/2) + Θ(n) | Θ(n log n) |
| Average | random input or random pivot | expected ≈ 1.39 n log2 n comparisons | Θ(n log n) |
| Worst | pivot 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.
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.
Heap sort works in two phases:
- The array is turned into a max-heap.
- 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.
| Step | Array (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.
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.
| Step | Node | Swaps | Array |
|---|---|---|---|
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.
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.
| Round | Root ↔ last | Sift | Heap | Sorted region |
|---|---|---|---|---|
| 1 | 8 ↔ 1 | 1 ↔ 7, 1 ↔ 3 | [7, 6, 3, 4, 5, 1, 2] | [8] |
| 2 | 7 ↔ 2 | 2 ↔ 6, 2 ↔ 5 | [6, 5, 3, 4, 2, 1] | [7, 8] |
| 3 | 6 ↔ 1 | 1 ↔ 5, 1 ↔ 4 | [5, 4, 3, 1, 2] | [6, 7, 8] |
| 4 | 5 ↔ 2 | 2 ↔ 4 | [4, 2, 3, 1] | [5, 6, 7, 8] |
| 5 | 4 ↔ 1 | 1 ↔ 3 | [3, 2, 1] | [4, 5, 6, 7, 8] |
| 6 | 3 ↔ 1 | 1 ↔ 2 | [2, 1] | [3, 4, 5, 6, 7, 8] |
| 7 | 2 ↔ 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].
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
}
}heapSortconsists of two loops. The first builds the heap:idecreases from the last internal noden / 2 - 1to the root, andheapify(a, n, i)is called for each node.- The second loop sorts:
idecreases from the last index to 1. In each round the root is swapped witha[i]. Thenheapify(a, i, 0)is called; the second argumentisays that the heap now consists only of the firstielements. The elements already moved to the end are thus not reused in sifting. heapifysifts nodeidown in a heap of sizen. First the index of the largest amongiand its left and right children is found inlargest. The checksleft < nandright < nask 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 = largestis set, and thewhileloop 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).
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
}
}| Call / round | Checks | largest | Action | a |
|---|---|---|---|---|
heapify(6, 2) | left = 5 (5) > 2: yes; right = 6 ≥ n | 5 | swap(2, 5) | [3, 9, 5, 1, 4, 2] |
↳ i = 5 (loop continues) | left = 11 ≥ n | 5 | sifting ends | [3, 9, 5, 1, 4, 2] |
heapify(6, 1) | left = 3 (1) > 9: no; right = 4 (4) > 9: no | 1 | no change | [3, 9, 5, 1, 4, 2] |
heapify(6, 0) | left = 1 (9) > 3: yes; right = 2 (5) > 9: no | 1 | swap(0, 1) | [9, 3, 5, 1, 4, 2] |
↳ i = 1 (loop continues) | left = 3 (1) > 3: no; right = 4 (4) > 3: yes | 4 | swap(1, 4) | [9, 4, 5, 1, 3, 2] |
↳ i = 4 (loop continues) | left = 9 ≥ n | 4 | sifting 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.
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.
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- The first loop zeroes all the counters.
- 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. - 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. - 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.
| Loop | Step | Action | C | B |
|---|---|---|---|---|
| 1 | — | counters are zeroed | [0, 0, 0, 0] | [–, –, –, –, –] |
| 2 | j = 1 | A[1] = 4, C[4]++ | [0, 0, 0, 1] | |
| 2 | j = 2 | A[2] = 1, C[1]++ | [1, 0, 0, 1] | |
| 2 | j = 3 | A[3] = 3, C[3]++ | [1, 0, 1, 1] | |
| 2 | j = 4 | A[4] = 4, C[4]++ | [1, 0, 1, 2] | |
| 2 | j = 5 | A[5] = 3, C[3]++ | [1, 0, 2, 2] | |
| 3 | i = 2 | C[2] = 0 + 1 | [1, 1, 2, 2] | |
| 3 | i = 3 | C[3] = 2 + 1 | [1, 1, 3, 2] | |
| 3 | i = 4 | C[4] = 2 + 3 | [1, 1, 3, 5] | |
| 4 | j = 5 | A[5] = 3 → B[3] | [1, 1, 2, 5] | [–, –, 3, –, –] |
| 4 | j = 4 | A[4] = 4 → B[5] | [1, 1, 2, 4] | [–, –, 3, –, 4] |
| 4 | j = 3 | A[3] = 3 → B[2] | [1, 1, 1, 4] | [–, 3, 3, –, 4] |
| 4 | j = 2 | A[2] = 1 → B[1] | [0, 1, 1, 4] | [1, 3, 3, –, 4] |
| 4 | j = 1 | A[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.
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
| Loop | Work | Time |
|---|---|---|
| 1 | C[1..k] = 0 | Θ(k) |
| 2 | counting | Θ(n) |
| 3 | prefix sums | Θ(k) |
| 4 | placing 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].
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;
}radixSortgrows the variableexpas 1, 10, 100, and so on. The conditionmax / exp > 0holds as long as the largest number still has an unprocessed digit. For 802,exptakes the values 1, 10, and 100; at 1000, 802/1000 = 0 and the loop ends.expis of typelong: if max is 109 or larger,exp *= 10on anintwould overflow and the loop could continue wrongly. Like counting sort, the code is meant only for non-negative integers.countByDigitis counting sort adapted to a single digit. The digit of a number is found with(x / exp) % 10: for 802 atexp = 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 whatcount[x] − 1does in the Java version of counting sort.
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.
- 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.
- 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).
- Hundreds digit: [2, 24, 45, 66, 75, 90, 170, 802]. All digits have been processed and the array is sorted.
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.
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.
| Stage | Action | count[0..5] | out |
|---|---|---|---|
| counting | digits 2, 5, 1, 3, 1 | [0, 2, 1, 1, 0, 1] | [–, –, –, –, –] |
| prefix | prefix sums | [0, 2, 3, 4, 4, 5] | [–, –, –, –, –] |
i = 4 | 11, d = 1, --count[1] = 1 | [0, 1, 3, 4, 4, 5] | [–, 11, –, –, –] |
i = 3 | 23, d = 3, --count[3] = 3 | [0, 1, 3, 3, 4, 5] | [–, 11, –, 23, –] |
i = 2 | 41, d = 1, --count[1] = 0 | [0, 0, 3, 3, 4, 5] | [41, 11, –, 23, –] |
i = 1 | 15, d = 5, --count[5] = 4 | [0, 0, 3, 3, 4, 4] | [41, 11, –, 23, 15] |
i = 0 | 32, 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.
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_RUNand 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.
sizeis 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 < hidoes 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).
| Step | Action | Array |
|---|---|---|
| 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 = 4 | lo = 8: mid = 11 ≥ hi = 9, no partner | unchanged |
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.
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
| Algorithm | Best | Average | Worst | Extra memory | Stable | In place |
|---|---|---|---|---|---|---|
| Bubble (with flag) | Θ(n) | Θ(n²) | Θ(n²) | O(1) | Yes | Yes |
| Insertion | Θ(n) | Θ(n²) | Θ(n²) | O(1) | Yes | Yes |
| Selection | Θ(n²) | Θ(n²) | Θ(n²) | O(1) | No | Yes |
| Shell (n/2 gaps) | Θ(n log n) | depends on gaps | Θ(n²) | O(1) | No | Yes |
| Merge | Θ(n log n) | Θ(n log n) | Θ(n log n) | Θ(n) | Yes | No |
| Quicksort | Θ(n log n) | Θ(n log n) | Θ(n²) | O(log n)* | No | Yes |
| Heap sort | O(n log n) | Θ(n log n) | Θ(n log n) | O(1) | No | Yes |
| Counting | Θ(n + k) | Θ(n + k) | Θ(n + k) | Θ(n + k) | Yes | No |
| Radix (LSD) | Θ(d(n + b)) | Θ(d(n + b)) | Θ(d(n + b)) | Θ(n + b) | Yes | No |
| Bucket | Θ(n) | Θ(n)† | Θ(n²) | Θ(n) | Yes | No |
| Timsort | Θ(n) | Θ(n log n) | Θ(n log n) | O(n) | Yes | No |
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.
| Algorithm | Random | Sorted | Reverse sorted |
|---|---|---|---|
| Bubble (with flag) | 497,960 | 999 | 499,500 |
| Insertion | 252,205 | 999 | 499,500 |
| Selection | 499,500 | 499,500 | 499,500 |
| Shell (n/2) | 14,723 | 8,006 | 11,716 |
| Merge | 8,693 | 5,044 | 4,932 |
| Quicksort (last element as pivot) | 11,384 | 499,500 | 499,500 |
| Heap sort | 16,791 | 17,583 | 15,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.
| Mistake | Consequence | Correct form |
|---|---|---|
| Running past the array bound | Writing j < n in bubble sort makes a[j+1] fall outside the array. | j < n - 1 - i |
| Not saving the key | In insertion sort the first shift overwrites the element being inserted. | key = a[i] before the loop |
| Keeping the minimum as a value | In 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 recursion | quickSort(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 size | Elements 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
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 atj = −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.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.
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.
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 swapa[2] ↔ a[4]gives [3, 1, 4, 6, 7]. The method returns 2; the pivot 4 is in its final place at index 2.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.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.
The Java method
countingSortis called with [1, 0, 2, 1, 0]. What is thecountarray 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).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.
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
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022.
- E. D. Demaine, C. E. Leiserson, MIT 6.046J Introduction to Algorithms lecture notes, 2005.
- C. A. R. Hoare, "Quicksort", The Computer Journal 5(1), 1962.
- D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998.
- T. Peters, "listsort.txt" (Timsort design note), CPython, 2002.
- R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011.
- 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.