Advanced Sorting: Merge, Quick, and Heap Sort

The key step: merging two sorted piles

Two helpers hand back two sorted piles, face up: 10, 14, 29 and 13, 37. To make one sorted pile, you only ever look at the top paper of each pile: take the smaller one, and repeat. When one pile is empty, put the rest of the other pile at the end. Those are the leftovers, and they need no more comparisons.

Merging two piles with a total of n values takes at most n - 1 comparisons. That is the cheap part.

The whole sort by hand

On paper, write the split rows going down until every part has one value, then the merge rows going back up. When a part has an odd number of values, the left half gets the extra one (like mid in binary search: (low + high) / 2, rounded down).

Merge sort in Java

The code has two methods. mergeSort does the splitting with recursion; merge does the merging. Both work on a part of the array, from index low to index high, so the first call is mergeSort(arr, 0, arr.length - 1). Both are static void .

 1static void mergeSort(int[] arr, int low, int high) { 2  if (low >= high) { 3    return;                          // base case: 0 or 1 value 4  } 5  int mid = (low + high) / 2; 6  mergeSort(arr, low, mid);          // sort the left half 7  mergeSort(arr, mid + 1, high);     // sort the right half 8  merge(arr, low, mid, high);        // merge the two sorted halves 9}

Now the merge method, on the last merge of the five scores. It is long, but it is just the "two piles" steps from above, in code:

 1static void merge(int[] arr, int low, int mid, int high) { 2  int[] temp = new int[high - low + 1]; 3  int i = low;                       // next value in the left half 4  int j = mid + 1;                   // next value in the right half 5  int k = 0;                         // next empty slot in temp 6  while (i <= mid && j <= high) { 7    if (arr[i] <= arr[j]) { 8      temp[k] = arr[i]; 9      i++;10    } else {11      temp[k] = arr[j];12      j++;13    }14    k++;15  }16  while (i <= mid) {                 // leftovers from the left half17    temp[k] = arr[i];18    i++;19    k++;20  }21  while (j <= high) {                // leftovers from the right half22    temp[k] = arr[j];23    j++;24    k++;25  }26  for (k = 0; k < temp.length; k++) {27    arr[low + k] = temp[k];          // copy back into arr28  }29}

Some lines are new. Here is how to read them aloud:

Quick sort in Java

quickSort is short, because partition does the work. Compare it with mergeSort: here the work (partition) comes before the two recursive calls.

 1static void quickSort(int[] arr, int low, int high) {
 2  if (low >= high) {
 3    return;                          // base case: 0 or 1 value
 4  }
 5  int p = partition(arr, low, high); // the pivot's final index
 6  quickSort(arr, low, p - 1);        // sort the smaller values
 7  quickSort(arr, p + 1, high);       // sort the bigger values
 8}

The first call is quickSort(arr, 0, arr.length - 1). Here is the first partition of the five scores:

 1static int partition(int[] arr, int low, int high) { 2  int pivot = arr[high];             // the last value is the pivot 3  int i = low;                       // where the next smaller value goes 4  for (int j = low; j < high; j++) { 5    if (arr[j] < pivot) { 6      int temp = arr[i];             // swap arr[i] and arr[j] 7      arr[i] = arr[j]; 8      arr[j] = temp; 9      i++;10    }11  }12  int temp = arr[i];                 // put the pivot in its place13  arr[i] = arr[high];14  arr[high] = temp;15  return i;16}

partition changes the array and returns a value: the pivot's index, so quickSort knows where the two parts are.

Quick sort's weak spot

Quick sort is fast when each pivot splits its part into two halves of about the same size. But what if the array is already sorted?

With our last-value pivot, a sorted array of 1,000 values takes 499,500 comparisons, the same as bubble sort. Real programs avoid this by picking the middle value or a random value as the pivot (and swapping it to the end first). Then a bad split is very unlikely.

First: a tree of values

The bracket is a tree: values connected from the top down. You studied trees in the Trees lesson (midterm); for heap sort you only need these words:

A heap is stored in a plain array. Read the array from left to right and fill the tree row by row, from left to right: index 0 is the root, index 1 and 2 are its children, and so on. No links are needed, because a simple rule finds every child:

Heap sort by hand

The main move is sift down: a value that is too small for its spot swaps with its bigger child, again and again, until it is at least as big as its children (or has none). Heap sort has two steps:

1. Build a max-heap. Sift down every parent, starting from the last parent (index n / 2 - 1) back to the root.
2. Take the biggest out, again and again. Swap the root (the biggest) with the last value of the heap. That value is now in its final place, at the end, and leaves the heap. Sift the new root down to repair the heap. Repeat until the heap has one value.

It is selection sort's idea ("find the biggest, put it at the end"), but the heap finds the biggest with a few swaps along one path instead of a whole pass. Watch the tree and the array change together:

Heap sort in Java

heapSort follows the two steps. It uses no recursion: the sifting is a while loop.

 1static void heapSort(int[] arr) {
 2  int n = arr.length;
 3  for (int i = n / 2 - 1; i >= 0; i--) {
 4    siftDown(arr, i, n);             // step 1: build a max-heap
 5  }
 6  for (int end = n - 1; end > 0; end--) {
 7    int temp = arr[0];               // step 2: swap the root (biggest)
 8    arr[0] = arr[end];               //   with the last value in the heap
 9    arr[end] = temp;
10    siftDown(arr, 0, end);           // repair the smaller heap
11  }
12}

Here is siftDown, right after 37 was swapped to the end (the heap is now index 0 to 3):

 1static void siftDown(int[] arr, int i, int size) { 2  while (2 * i + 1 < size) {         // while i has a left child 3    int child = 2 * i + 1;           // the left child 4    if (child + 1 < size && arr[child + 1] > arr[child]) { 5      child++;                       // the right child is bigger 6    } 7    if (arr[i] >= arr[child]) { 8      return;                        // parent is big enough: stop 9    }10    int temp = arr[i];               // swap parent and bigger child11    arr[i] = arr[child];12    arr[child] = temp;13    i = child;                       // keep going down14  }15}

The parameter size matters: values at index size and beyond are already sorted, so siftDown must not treat them as children.

Which ones are stable?

Remember stable sorting ? Here is a short class list, already in A-to-Z order. Ana and Cris tie at 85. Here it is sorted by grade with each sort:

Merge sort is stable because on a tie it takes from the left half (<=). In quick sort, Ben (smaller than the pivot Cris) swaps with Ana, and then the pivot swaps into Ana's new spot, which throws Ana behind Cris. In heap sort, the root Ana is swapped straight to the end, past Cris. Long jumps like these can carry a value past an equal one.

Which sort when?

Here are all six sorts from the two lessons, by situation:

What Arrays.sort uses

Java's own sort, which you met in Basic sorting, picks a method by the kind of array:

int[] scores = {29, 10, 14, 37, 13};
Arrays.sort(scores);                          // ints: a fast quick sort (dual-pivot)
String[] names = {"Mia", "Ana", "Joy", "Ben"};
Arrays.sort(names);                           // objects: a stable merge sort

For numbers (int[], double[]), Java uses a dual-pivot quick sort (two pivots, three parts). Equal numbers look the same, so stability does not matter. For objects (String[], records), it uses a stable merge sort called TimSort, so ties keep their order.

All three in one program

Here are the three sorts in one runnable file. Run it, and check that each line prints the sorted scores:

 1import java.util.Arrays;
 2
 3public class Main {
 4  static void mergeSort(int[] arr, int low, int high) {
 5    if (low >= high) {
 6      return;
 7    }
 8    int mid = (low + high) / 2;
 9    mergeSort(arr, low, mid);
10    mergeSort(arr, mid + 1, high);
11    merge(arr, low, mid, high);
12  }
13
14  static void merge(int[] arr, int low, int mid, int high) {
15    int[] temp = new int[high - low + 1];
16    int i = low;
17    int j = mid + 1;
18    int k = 0;
19    while (i <= mid && j <= high) {
20      if (arr[i] <= arr[j]) {
21        temp[k] = arr[i];
22        i++;
23      } else {
24        temp[k] = arr[j];
25        j++;
26      }
27      k++;
28    }
29    while (i <= mid) {
30      temp[k] = arr[i];
31      i++;
32      k++;
33    }
34    while (j <= high) {
35      temp[k] = arr[j];
36      j++;
37      k++;
38    }
39    for (k = 0; k < temp.length; k++) {
40      arr[low + k] = temp[k];
41    }
42  }
43
44  static void quickSort(int[] arr, int low, int high) {
45    if (low >= high) {
46      return;
47    }
48    int p = partition(arr, low, high);
49    quickSort(arr, low, p - 1);
50    quickSort(arr, p + 1, high);
51  }
52
53  static int partition(int[] arr, int low, int high) {
54    int pivot = arr[high];
55    int i = low;
56    for (int j = low; j < high; j++) {
57      if (arr[j] < pivot) {
58        int temp = arr[i];
59        arr[i] = arr[j];
60        arr[j] = temp;
61        i++;
62      }
63    }
64    int temp = arr[i];
65    arr[i] = arr[high];
66    arr[high] = temp;
67    return i;
68  }
69
70  static void heapSort(int[] arr) {
71    int n = arr.length;
72    for (int i = n / 2 - 1; i >= 0; i--) {
73      siftDown(arr, i, n);
74    }
75    for (int end = n - 1; end > 0; end--) {
76      int temp = arr[0];
77      arr[0] = arr[end];
78      arr[end] = temp;
79      siftDown(arr, 0, end);
80    }
81  }
82
83  static void siftDown(int[] arr, int i, int size) {
84    while (2 * i + 1 < size) {
85      int child = 2 * i + 1;
86      if (child + 1 < size && arr[child + 1] > arr[child]) {
87        child++;
88      }
89      if (arr[i] >= arr[child]) {
90        return;
91      }
92      int temp = arr[i];
93      arr[i] = arr[child];
94      arr[child] = temp;
95      i = child;
96    }
97  }
98
99  public static void main(String[] args) {
100    int[] a = {29, 10, 14, 37, 13};
101    mergeSort(a, 0, a.length - 1);
102    System.out.println(Arrays.toString(a));   // [10, 13, 14, 29, 37]
103
104    int[] b = {29, 10, 14, 37, 13};
105    quickSort(b, 0, b.length - 1);
106    System.out.println(Arrays.toString(b));   // [10, 13, 14, 29, 37]
107
108    int[] c = {29, 10, 14, 37, 13};
109    heapSort(c);
110    System.out.println(Arrays.toString(c));   // [10, 13, 14, 29, 37]
111  }
112}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

Coding task: finish merge

The merge method below is missing its two leftover loops. Write them (about 10 short lines), then run the file. All three lines should match the expected output.

 1import java.util.Arrays;
 2
 3public class Main {
 4  static void merge(int[] arr, int low, int mid, int high) {
 5    int[] temp = new int[high - low + 1];
 6    int i = low;
 7    int j = mid + 1;
 8    int k = 0;
 9    while (i <= mid && j <= high) {
10      if (arr[i] <= arr[j]) {
11        temp[k] = arr[i];
12        i++;
13      } else {
14        temp[k] = arr[j];
15        j++;
16      }
17      k++;
18    }
19    // YOUR CODE: copy the leftovers of the left half into temp.
20
21    // YOUR CODE: copy the leftovers of the right half into temp.
22
23    for (k = 0; k < temp.length; k++) {
24      arr[low + k] = temp[k];
25    }
26  }
27
28  public static void main(String[] args) {
29    int[] a = {10, 14, 29, 13, 37};
30    merge(a, 0, 2, 4);
31    System.out.println(Arrays.toString(a));  // expected: [10, 13, 14, 29, 37]
32    int[] b = {40, 50, 60, 1, 2};
33    merge(b, 0, 2, 4);
34    System.out.println(Arrays.toString(b));  // expected: [1, 2, 40, 50, 60]
35    int[] c = {7, 30};
36    merge(c, 0, 0, 1);
37    System.out.println(Arrays.toString(c));  // expected: [7, 30]
38  }
39}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

while (i <= mid) {        // leftovers from the left half
  temp[k] = arr[i];
  i++;
  k++;
}
while (j <= high) {       // leftovers from the right half
  temp[k] = arr[j];
  j++;
  k++;
}