Merge Sort
/*************************************************************************
 * Copyright © 2006, Robert Sedgewick and Kevin Wayne.  
 *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);
    }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License