In JAVA; create an array of CheckBook objects. Display the checks by CheckNumber in UNSORTED order. Apply the Mergsort and Display the checks by checkNumber in SORTED order.

public class TestMerge {

public static void main (String [ ] args ) {

***Create your array of Strings with AT LEAST 5 names

System.out.println ( " ____________________________");

***LOOP through your array and print out each UNSORTED string

System.out.println ( " ____________________________");

Merge.sort (words);

***LOOP through your array and print out each SORTED string

System.out.println ( " ____________________________");

}

}

Output:

Dan $ 500.00 #104

James $ 95.00 #107

Hank $ 260.00 #101

Dillion $ 195.00 #100

Lilly $ 385.00 #099

___________________

Lilly $ 385.00 #099

Dillion $ 195.00 #100

Hank $ 260.00 #101

Dan $ 500.00 #104

James $ 95.00 #107

Merg.sort function & helper:

import edu.princeton.cs.algs4.StdOut;

public class Merge {

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

// 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++]; }

// postcondition: a[lo .. hi] is sorted assert isSorted(a, lo, hi); }

// mergesort a[lo..hi] using auxiliary array aux[lo..hi] private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) { 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); }

/** * Rearranges the array in ascending order, using the natural order. * @param a the array to be sorted */ public static void sort(Comparable[] a) { Comparable[] aux = new Comparable[a.length]; sort(a, aux, 0, a.length-1); assert isSorted(a); }

/*************************************************************************** * Helper sorting functions. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } // exchange a[i] and a[j] private static void exch(Object[] a, int i, int j) { Object swap = a[i]; a[i] = a[j]; a[j] = swap; }

/*************************************************************************** * Check if array is sorted - useful for debugging. ***************************************************************************/ private static boolean isSorted(Comparable[] a) { return isSorted(a, 0, a.length - 1); }

private static boolean isSorted(Comparable[] a, int lo, int hi) { for (int i = lo + 1; i <= hi; i++) if (less(a[i], a[i-1])) return false; return true; }

/*************************************************************************** * 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) {

// 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++]; } }

/** * Returns a permutation that gives the elements in the array in ascending order. * @param a the array * @return a permutation p[] such that a[p[0]], a[p[1]], * ..., a[p[N-1]] are in ascending order */ public static int[] indexSort(Comparable[] a) { 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; }

// mergesort a[lo..hi] using auxiliary array aux[lo..hi] private static void sort(Comparable[] a, int[] index, int[] aux, int lo, int hi) { 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); }

// print array to standard output private static void show(Comparable[] a) { for (int i = 0; i < a.length; i++) { StdOut.println(a[i]); } } }