23.1. Sorting II¶
23.1.1. Merge Sort¶
A natural approach to problem solving is divide and conquer. To use divide and conquer when sorting, we might consider breaking the list to be sorted into pieces, process the pieces, and then put them back together somehow. One way to do this would be to split the list in half, sort the halves, and then merge the sorted halves together. This is the idea behind merge sort. We give the pseudocode for the process below:
public static void mergesort(T[] values) {
if (values.length <= 1) return; // base case, array is sorted
else {
// split the array into two halves and copy their contents
left = left half of the items from values;
right = right half of the items from values;
// recursively sort the halves
mergesort(left);
mergesort(right);
// merge the halves together and store the result in values
merge(values, left, right);
}
}
23.1.1.1. merge()¶
We first look at the merge operation, which takes two smaller, sorted arrays and combines them into a single larger sorted array. It begins by examining the first record of each smaller array and picks the smaller value as the smallest record overall. This smaller value is then copied into the output array. Merging continues in this way, comparing the next records of the smaller arrays and continually appending the smaller to the output array until no more input records remain:
private void merge(T[] result, T[] a, T[] b) {
// Index of next value to compare in a
int left = 0;
// Index of next value to compare in b
int right = 0;
// Index of next slot to fill in sorted
int next = 0;
// Keep comparing values in a and b until we run out of values in one
// of the arrays
while (left < a.length && right < b.length) {
// Move the smaller value to sorted
if (a[left].compareTo(b[right]) < 0) {
result[next] = a[left];
left++;
} else {
result[next] = b[right];
right++;
}
next++;
}
// If there are values left in a, copy the rest of them to sorted
for (; left < a.length; left++) {
result[next] = a[left];
next++;
}
// If there are values left in b, copy the rest of them to sorted
for (; right < b.length; right++) {
result[next] = b[right];
next++;
}
}
In the worst case, the two halves of the array are of size \(n/2\), so the merge operation requires \(O(n)\) time as there are \(n\) records to be copied.
23.1.1.2. mergesort() implementation¶
Below is the complete implementation of mergesort:
Note
We use the built-in System.arraycopy() method to copy the values into the smaller left and right arrays. This is an \(O(n)\) operation!
public void mergesort(T[] values) {
// Base case: values contains 0 or 1 int. Return without
// doing anything since values is already sorted in that case.
if (values.length <= 1) {
return;
}
// Recursive case: there are at least 2 values, so we need to sort them
else {
// Split the array into 2 equal-sized parts
int middle = values.length / 2;
T[] left = (T[]) (new Comparable[middle]);
T[] right = (T[]) (new Comparable[values.length - middle]);
System.arraycopy(values, 0, left, 0, left.length);
System.arraycopy(values, middle, right, 0, right.length);
// Recursively sort the halves
mergesort(left);
mergesort(right);
// Merge the sorted halves together
merge(values, left, right);
}
}
23.1.2. Runtime comparisons between sorting algorithms¶
Note
We will not cover bubble sort or quick sort this semester – they are listed here for reference.
Sorting Algorithm |
Time Complexity |
Memory Usage |
|---|---|---|
Selection sort |
$O(n^2)$ |
In-place swaps |
Insertion sort |
$O(n^2)$ |
In-place swaps |
Bubble sort |
$O(n^2)$ |
In-place swaps |
Merge sort |
$O(n log n)$ |
Copies array |
Quick sort |
$O(n log n)$ on avg. |
In-place swaps |