17. Mergesort
Mergesort runs in \(O(N\log N)\) worst-case running time.
It is a divide-and-conquer recursive algorithm.
The number of comparisons is nearly optimal.
17.1. Divide-And-Conquer
Divide-And-Conquer is very important strategy in computer science.
It is able to solve large problem in \(O(N \log N)\).
The idea is simple:
Breaking the problem into smaller sub-problems
Solving the sub-problems
Combine the sub-problem that are solved
17.2. Mergesort
In the case of Mergesort the divide-and-conquer strategy is straight-forward.
We take our array that we need to sort.
We split the array recursively in two until each array contains only one element.
Then, merge the arrays by sorting them.
Example
Following is an example for the array
[1,26,24,13,2,38,27,15]
.
17.3. The Algorithm
The algorithm is simple.
The merge function is based on the fact that each list are sorted before being merged.
Below the code for mergesort.
1/**
2 Implements the recursive merge sort algorithm.
3 In this version, copies of the subtables are made, sorted, and then merged.
4 */
5public class MergeSort {
6 /** Sort the array using the merge sort algorithm.
7 pre: table contains Comparable objects.
8 post: table is sorted.
9 @param table The array to be sorted
10 */
11 public static <T extends Comparable<T>> void sort(T[] table) {
12 // A table with one element is sorted already.
13 if (table.length > 1) {
14 // Split table into halves.
15 int halfSize = table.length / 2;
16 T[] leftTable = (T[]) new Comparable[halfSize];
17 T[] rightTable = (T[]) new Comparable[table.length - halfSize];
18 System.arraycopy(table, 0, leftTable, 0, halfSize);
19 System.arraycopy(table, halfSize, rightTable, 0, table.length - halfSize);
20 // Sort the halves.
21 sort(leftTable);
22 sort(rightTable);
23 // Merge the halves.
24 merge(table, leftTable, rightTable);
25 }
26 }
27
28 /** Merge two sequences.
29 @pre leftSequence and rightSequence are sorted.
30 @post outputSequence is the merged result and is sorted.
31 @param outputSequence The destination
32 @param leftSequence The left input
33 @param rightSequence The right input
34 */
35 private static <T extends Comparable<T>> void merge(T[] outputSequence, T[] leftSequence, T[] rightSequence) {
36 int i = 0;
37 // Index into the left input sequence.
38 int j = 0;
39 // Index into the right input sequence.
40 int k = 0;
41 // Index into the output sequence.
42 // While there is data in both input sequences
43 while (i < leftSequence.length && j < rightSequence.length) {
44 // Find the smaller and
45 // insert it into the output sequence.
46 if (leftSequence[i].compareTo(rightSequence[j]) < 0) {
47 outputSequence[k++] = leftSequence[i++];
48 } else {
49 outputSequence[k++] = rightSequence[j++];
50 }
51 }
52
53 // assert: one of the sequences has more items to copy.
54 // Copy remaining input from left sequence into the output.
55 while (i < leftSequence.length) {
56 outputSequence[k++] = leftSequence[i++];
57 }
58
59 // Copy remaining input from right sequence into output.
60 while (j < rightSequence.length) {
61 outputSequence[k++] = rightSequence[j++];
62 }
63 }
64
65}