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); } }
page revision: 1, last edited: 02 Jul 2008 20:47