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].

../../_images/divide-merge.png

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}