Uses Algs4.java from princeton. But don't know how to submit the file.

• Create a package called ceMerge Add class MergeSlow and class MergeComparison that includes the main method.
• Class MergeSlow:
  • Copy the implementation from class Merge (Links to an external site.) as a starter code, and make the necessary changes so that it compiles.
  • Find the public method sort. It calls the recursive method sort. However, before it does so, it creates an auxiliary array and passes it as the second argument. This is a very important step. It allows the recursive method to reuse the same auxiliary array over and over again.
  • In this exercise, we explore what happens when we don't pass the auxiliary array. Change the recursive sort method header and remove the second parameter (the auxiliary array). To make the method compile, remove the argument aux when calling the methods sort and also when calling merge. This impacts the method merge. Remove the second parameter (the auxiliary array) from the method merge. Since the array aux is needed for merging, create it as the first statement in the body of the method merge. There is still a syntax error we need to fix. Now that we changed the signature of the recursive method sort, the method call in the public sort method no longer compiles. Fix the problem by removing the second argument (aux) and delete the statement above that creates the auxiliary array. It is no longer needed in the public sort method. At this point, class MergeSlow should compile.
• Class MergeComparison In this class, we will time how long it takes to sort multiple number arrays of various sizes using Merge sort. Then we'll repeat the experiment using the modified class MergeSlow. Take-Away: Even an efficient algorithm can have a dismal performance if we don't implement it efficiently.
  1. Write a method called getNumbers. It has one parameter, which is the array size, and it returns an array that is initialized with random 6-digit numbers.
  2. Create an Integer array and initialize it with 1024 random 6-digit numbers.
  3. Use the method nanoTime from class System to measure how long it takes to sort the array with the original merges sort from class Merge.
  4. Print the size of the array and the time it took to sort it. The duration should be measured in seconds and it should display 3 digits after the decimal point.
  5. Repeat 2 - 4 nine times. However, each time, create an array of twice the size as before.
  6. Print the output in straight columns as shown in the Sample Output. Include a header that indicates that we used Professor Sedgewick's class Merge to sort the array.
  7. Repeat 2 - 6. However, this time use the sort method from class MergeSlow. Use white space to group related output as shown in the Sample Output. Notice how the performance starts to deteriorate as the array size increases. If you can't see a significant performance difference in your output, increase the initial number of array elements.

Sample Output

n Merge ---------- ------------ 1,024 0.0067s 2,048 0.0024s 4,096 0.0034s 8,192 0.0069s 16,384 0.0311s 32,768 0.0460s 65,536 0.2324s 131,072 0.3225s 262,144 0.2653s n MergeSlow ---------- ------------ 1,024 0.0398s 2,048 0.0231s 4,096 0.0310s 8,192 0.0891s 16,384 0.3560s 32,768 0.9029s 65,536 2.1249s 131,072 49.8824s 262,144 212.2430s

This are the copy class merge it uses also algs4.java from princeton to process StdOut

/****************************************************************************** * Compilation: javac Merge.java * Execution: java Merge < input.txt * Dependencies: StdOut.java StdIn.java * Data files: https://algs4.cs.princeton.edu/22mergesort/tiny.txt * https://algs4.cs.princeton.edu/22mergesort/words3.txt * * Sorts a sequence of strings from standard input using mergesort. * * % more tiny.txt * S O R T E X A M P L E * * % java Merge < tiny.txt * A E E L M O P R S T X [ one string per line ] * * % more words3.txt * bed bug dad yes zoo ... all bad yet * * % java Merge < words3.txt * all bad bed bug dad ... yes yet zoo [ one string per line ] * ******************************************************************************/

/** * The {@code Merge} class provides static methods for sorting an * array using a top-down, recursive version of mergesort. *

* This implementation takes (n log n) time * to sort any array of length n (assuming comparisons * take constant time). It makes between * ~ n log₂n and * ~ 1 n log₂n compares. *

* This sorting algorithm is stable. * It uses (n) extra memory (not including the input array). *

* For additional documentation, see * Section 2.2 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * For an optimized version, see {@link MergeX}. * * @author Robert Sedgewick * @author Kevin Wayne */ public class MergeSlow {

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

// 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 function. ***************************************************************************/ // is v < w ? private static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } /*************************************************************************** * 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 {@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) { 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]); } }

/** * 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) { String[] a = StdIn.readAllStrings(); MergeSlow.sort(a); show(a); } }