Task 2: Understand How Bottom-Up Merge Sort Works

• 22. Make a table showing how the merge operations modify the array in sequential order (include the table in your PDF answer as text):
  • 25, 16, 21, 14, 26, 18, 23, 11, 20, 15, 22, 13, 17, 24, 12, 19
• 23. Pick a random array of 10 elements and make a merge table (include the table in your PDF answer as text) - do not pick a trivial array (e.g. 1, 2, 3... or 9, 8, 7, ...)

Task 3: Bottom-Up Merge Sort Method

• 31. In thesort.merge.bottomuppackage, make a public class named BottomUpMergeSort and a public class named BottomUpMergeSortTest
• 32. In the class BottomUpMergeSort make a publlic static method sort that receives the array to be sorted. It creates the auxiliary array to be used for merging and for each length of a subarray starting from 1 to n and doubling the length each time, merge the adjacent subarrays 2 by 2:.
  • Hint: See sort method inhttps://algs4.cs.princeton.edu/22mergesort/MergeBU.java.html
• 34. In the class BottomUpMergeSortTest, make a static method named sortTest that will perform and print the result of a single test for the method sort from BottomUpMergeSort class. It receives the name of the test, the array to be merged and the expected result. It prints the received input, the result obtained by calling sort on the input and if the test was succesful (the result is identical with the expected result). Returns true if they are identical.
• 35. In the class BottomUpMergeSortTest, make a static method named sortAllTests that will perform all the tests for sort method from class BottomUpMergeSort. It must call the previous method for sorting rrays each with the length of 0, 1, 2 (sorted), 2 (unsorted), 3 (sorted), 3 (decreasing), and 7. The values in the array must be random (do not use arrays like: 1, 2, 3, ... ). Do not use the same range for the arrays. The method must print at the end if all tests were successful or not.
• 36. In the class BottomUpMergeSortTest, make the main method and call the previous method. Check your resullts.