Merge Sort
```/*************************************************************************
*Compilation:  javac MergeSort.java
*  Execution:    java MergeSort N
*
*  A bare-bones N log N implementation of mergesort.
*
*  Remarks
*  ---------
*     - number of comparisons is guaranteed to be N log N
*     - sort is stable
*
*************************************************************************/

public class MergeSort {

/***********************************************************************
*  Merge the subarrays a[lo] .. a[mid-1] and a[mid] .. a[hi-1] into
*  a[lo] .. a[hi-1] using the auxilliary array aux[] as scratch space.
*
*  Precondition:   the two subarrays are in ascending order
*  Postcondition:  a[lo] .. a[hi-1] is in ascending order
*
***********************************************************************/
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
int i = lo, j = mid;
for (int k = lo; k < hi; k++) {
if      (i == mid)                 aux[k] = a[j++];
else if (j == hi)                  aux[k] = a[i++];
else if (a[j].compareTo(a[i]) < 0) aux[k] = a[j++];
else                               aux[k] = a[i++];
}

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

/***********************************************************************
*  Mergesort the subarray a[lo] .. a[hi-1], using the
*  auxilliary array aux[] as scratch space.
***********************************************************************/
public static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {

// base case
if (hi - lo <= 1) return;

// sort each half, recursively
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid, hi);

// merge back together
merge(a, aux, lo, mid, hi);
}

/***********************************************************************
*  Sort the array a using mergesort
***********************************************************************/
public static void sort(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N];
sort(a, aux, 0, N);
}

/***********************************************************************
*  Check if array is sorted - useful for debugging
***********************************************************************/
private static boolean isSorted(Comparable[] a) {
for (int i = 1; i < a.length; i++)
if (a[i].compareTo(a[i-1]) < 0) return false;
return true;
}

/***********************************************************************
*  Show results
***********************************************************************/
public static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++)
System.out.println(a[i]);
}

// test client
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);

// generate N random real numbers between 0 and 1
long start = System.currentTimeMillis();
Double[] a = new Double[N];
for (int i = 0; i < N; i++)
a[i] = Math.random();
long stop = System.currentTimeMillis();
double elapsed = (stop - start) / 1000.0;
System.out.println("Generating input:  " + elapsed + " seconds");

// sort them
start = System.currentTimeMillis();
sort(a);
stop = System.currentTimeMillis();
elapsed = (stop - start) / 1000.0;
System.out.println("Mergesort: " + elapsed + " seconds");
System.out.println(isSorted(a));

if (N < 100) show(a);
}
}
```
page revision: 1, last edited: 02 Jul 2008 20:47