5. Mergesort

Question 1

merging:

Answer 1

combining two ordered arrays to make one larger ordered array.

Question 2

mergesort

Answer 2

to sort an array, divide it into two halves, sort the two halves (recursively), and then merge the results.

Question 3

Mergesort guarantees to

Answer 3

sort an array of N items in time proportional to N log N, no matter what the input. Its prime disadvantage is that it uses extra space proportional to N.

Question 4

Abstract in-place merge.

Answer 4

The method merge(a, lo, mid, hi) in Merge.java puts the results of merging the subarrays a[lo..mid] with a[mid+1..hi] into a single ordered array, leaving the result in a[lo..hi]. While it would be desirable to implement this method without using a significant amount of extra space, such solutions are remarkably complicated. Instead, merge() copies everything to an auxiliary array and then merges back to the original.

Question 5

Top-down mergesort

Answer 5

Merge.java is a recursive mergesort implementation based on this abstract in-place merge. It is one of the best-known examples of the utility of the divide-and-conquer paradigm for efficient algorithm design.

Question 6

//Merge.java
/**
* The {@code Merge} class provides static methods for sorting an
* array using a top-down, recursive version of <em>mergesort</em>.
* <p>
* This implementation takes Θ(<em>n</em> log <em>n</em>) time
* to sort any array of length <em>n</em> (assuming comparisons
* take constant time). It makes between
* ~ ½ <em>n</em> log₂ <em>n</em> and
* ~ 1 <em>n</em> log₂ <em>n</em> compares.
* <p>
* This sorting algorithm is stable.
* It uses Θ(<em>n</em>) extra memory (not including the input array).
* <p>
*/
public class Merge {

Answer 6

// This class should not be instantiated.
private Merge() { }

Question 7

//Merge.java
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
assert isSorted(a, lo, mid);
assert isSorted(a, mid+1, hi);

    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];

Answer 7

// precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
assert isSorted(a, lo, mid);
assert isSorted(a, mid+1, hi);

    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k];
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }
    // postcondition: a[lo .. hi] is sorted
    assert isSorted(a, lo, hi);
}

Question 8

//Merge.java
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {

Answer 8

if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}

Question 9

//Merge.java
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {

Answer 9

Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
assert isSorted(a);
}

Question 10

//Merge.java
// is v < w ?
private static boolean less(Comparable v, Comparable w) {

Answer 10

return v.compareTo(w) < 0;
}

Question 11

//Merge.java
private static boolean isSorted(Comparable[] a) {

Answer 11

return isSorted(a, 0, a.length - 1);
}

Question 12

//Merge.java
private static boolean isSorted(Comparable[] a, int lo, int hi) {

Answer 12

for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}

Question 13

///Merge.java
*
* Index mergesort.
*/
// stably merge a[lo .. mid] with a[mid+1 .. hi] using aux[lo .. hi]
private static void merge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) {

Answer 13

// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = index[k];
}

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)                    index[k] = aux[j++];
        else if (j > hi)                     index[k] = aux[i++];
        else if (less(a[aux[j]], a[aux[i]])) index[k] = aux[j++];
        else                                 index[k] = aux[i++];
    }
}

Question 14

//Merge.java
/**
* Returns a permutation that gives the elements in the array in ascending order.
* @param a the array
* @return a permutation {@code p[]} such that {@code a[p[0]]}, {@code a[p[1]]},
* …, {@code a[p[n-1]]} are in ascending order
*/
public static int[] indexSort(Comparable[] a) {

Answer 14

int n = a.length;
int[] index = new int[n];
for (int i = 0; i < n; i++)
index[i] = i;

    int[] aux = new int[n];
    sort(a, index, aux, 0, n-1);
    return index;
}

Question 15

//Merge.java
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) {

Answer 15

if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, index, aux, lo, mid);
sort(a, index, aux, mid + 1, hi);
merge(a, index, aux, lo, mid, hi);
}

Question 16

//Merge.java
// print array to standard output
private static void show(Comparable[] a) {

Answer 16

for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}

Question 17

//Merge.java
/**
* Reads in a sequence of strings from standard input; mergesorts them;
* and prints them to standard output in ascending order.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {

Answer 17

String[] a = StdIn.readAllStrings();
Merge.sort(a);
show(a);
}
}

Question 18

Top-down mergesort uses between ______ and ___ compares and at most ___ array accesses to sort any array of length N.

Answer 18

Top-down mergesort uses between (1/2)Nlg N and NlgN compares and at most 6 N lg N array accesses to sort any array of length N.

Question 19

Improvements: Use insertion sort for small subarrays

Answer 19

We can improve most recursive algorithms by handling small cases differently. Switching to insertion sort for small subarrays will improve the running time of a typical mergesort implementation by 10 to 15 percent.

Question 20

Improvements: Test whether array is already in order.

Answer 20

We can reduce the running time to be linear for arrays that are already in order by adding a test to skip call to merge() if a[mid] is less than or equal to a[mid+1]. With this change, we still do all the recursive calls, but the running time for any sorted subarray is linear.

Question 21

Improvements: Eliminate the copy to the auxiliary array.

Answer 21

It is possible to eliminate the time (but not the space) taken to copy to the auxiliary array used for merging. To do so, we use two invocations of the sort method, one that takes its input from the given array and puts the sorted output in the auxiliary array; the other takes its input from the auxiliary array and puts the sorted output in the given array. With this approach, in a bit of mindbending recursive trickery, we can arrange the recursive calls such that the computation switches the roles of the input array and the auxiliary array at each level.

Question 22

Bottom-up mergesort.

Answer 22

Even though we are thinking in terms of merging together two large subarrays, the fact is that most merges are merging together tiny subarrays. Another way to implement mergesort is to organize the merges so that we do all the merges of tiny arrays on one pass, then do a second pass to merge those arrays in pairs, and so forth, continuing until we do a merge that encompasses the whole array. This method requires even less code than the standard recursive implementation. We start by doing a pass of 1-by-1 merges (considering individual items as subarrays of size 1), then a pass of 2-by-2 merges (merge subarrays of size 2 to make subarrays of size 4), then 4-by-4 merges, and so forth. MergeBU.java is an implementation of bottom-up mergesort.

Question 23

//MergeBU.java
/**
* The {@code MergeBU} class provides static methods for sorting an
* array using <em>bottom-up mergesort</em>. It is non-recursive.
* <p>
* This implementation takes Θ(<em>n</em> log <em>n</em>) time
* to sort any array of length <em>n</em> (assuming comparisons
* take constant time). It makes between
* ~ ½ <em>n</em> log₂ <em>n</em> and
* ~ 1 <em>n</em> log₂ <em>n</em> compares.
* <p>
* This sorting algorithm is stable.
* It uses Θ(<em>n</em>) extra memory (not including the input array).
*/
public class MergeBU {

Answer 23

// This class should not be instantiated.
private MergeBU() { }

Question 24

//MergeBU.java
// stably merge a[lo..mid] with a[mid+1..hi] using aux[lo..hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {

Answer 24

// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];  // this copying is unnecessary
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }

}

Question 25

//MergeBU.java
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {

Answer 25

int n = a.length;
Comparable[] aux = new Comparable[n];
for (int len = 1; len < n; len *= 2) {
for (int lo = 0; lo < n-len; lo += len+len) {
int mid = lo+len-1;
int hi = Math.min(lo+len+len-1, n-1);
merge(a, aux, lo, mid, hi);
}
}
assert isSorted(a);
}

Question 26

//MergeBU.java
// is v < w ?
private static boolean less(Comparable v, Comparable w) {

Answer 26

return v.compareTo(w) < 0;
}

Question 27

//MergeBU.java
private static boolean isSorted(Comparable[] a) {

Answer 27

for (int i = 1; i < a.length; i++)
if (less(a[i], a[i-1])) return false;
return true;
}

Question 28

//MergeBU.java
// print array to standard output
private static void show(Comparable[] a) {

Answer 28

for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}

Question 29

//MergeBU.java
/**
* Reads in a sequence of strings from standard input; bottom-up
* mergesorts them; and prints them to standard output in ascending order.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {

Answer 29

String[] a = StdIn.readAllStrings();
MergeBU.sort(a);
show(a);
}
}

Question 30

Bottom-up mergesort uses between ___ and ___ compares and at most ___ array accesses to sort any array of length N.

Answer 30

Bottom-up mergesort uses between 1/2 N lg N and N lg N compares and at most 6 N lg N array accesses to sort any array of length N.

Question 31

No compare-based sorting algorithm can guarantee to sort N items with fewer than ___ ~ ___ compares.

Answer 31

No compare-based sorting algorithm can guarantee to sort N items with fewer than lg(N!) ~ N lg N compares.

Question 32

Mergesort is an asymptotically optimal compare-based sorting algorithm.

Answer 32

That is, both the number of compares used by mergesort in the worst case and the minimum number of compares that any compare-based sorting algorithm can guarantee are ~N lg N.