AIT 512 A04-PA1 Top-Down Merge Sort

Task 1: Code Setup

• 11. Create a package “hw” (under src folder), if not already created.
• 12. Create a sub-package “a04” under the package “hw”.
• 13. Create a sub-package “a041” under the package “a04”.
• 14. In the sub-package “a041” copy your last version of the following classes: ArrayUtilitty, Stopwatch, TimeAnalysis
• Task 2: Understand How Top-Down Merge Sort Works

• 21. Watch the videos and read the materials related to how the top-down merge sort works.
• 22. Create 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 create 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: Merge Adjacent Sub-arrays using a Provided Auxiliary Array

• 31. In the “a041” package, create a public class named MergeArray and a public class named MergeArrayTest
• 32. In the class MergeArray, create a public static class method named mergeAux that will merge two adjacent sub-arrays already sorted and merge them in place. It receives the array containing the subarrays to be merged, the auxiliary array that can be used during merging, the start index of the first subarray, the end index of the first subarray and the end index of the second subarray. The second subarray starts just after the first one ends (copy the subarrays in the auxiliary array and then put back the elements in order, picking the min from the two subarrays).
• 33. In the class MergeArrayTest, create a static method named mergeAuxTest that will perform and print the result of a single test for the method mergeAux. It receives the name of the test, the array to be merged, the start1, end1 and end2 indexes and the expected result. It creates the auxiliary array before calling the merge. It prints the received input the result obtained by calling mergeAux and if the test was succesful (the result is identical with the expected result). Returns true if they are identical.
  • 
    
  • 34. In the class MergeArrayTest, create a static method named mergeAuxAllTests that will perform all the tests for mergeAux. It must call the previous method for merging two subarrays each with both of the length of 1, 2, 3, 5 and one test with the length of 6 for first subarray and 7 for the second subarray. Some will start from the left, some will be at the right and some in the middle of the enclosed array. Pick various values for start and end parameters. The values in the array must be random. Do not use the same range for the arrays. The method must print at the end if all tests were successful or not. Be sure your test sub-array are sorted.
    
• • 
    
  • 35. In the class MergeArrayTest, create the main method and call the previous method. Check your resullts. Test and debug until your examples work well. Include a text with the obtained correct results in your PDF submission.
    
  • 
    
• • Task 4: Top-Down Merge Sort Method

• 41. In the “a041” package, create a public class named TopDownMergeSort and a public class named TopDownMergeSortTest
• 42. In the class TopDownMergeSort create a private recursive static method sort that receives an array to be sorted, an auxiliary array to be used for merging and the start and end index of the elements to be sorted. After checking that the indexes are correct, compute the middle point, call recursively the same method to sort the left and right array and then merge the results using the method in the previous task.
  • 
    
• 43. In the class TopDownMergeSort create a publlic static method sort that receives the array to be sorted. It creates the auxiliary array to be used for merging and calls the method in the previous step for the entire array.
  • Hint:
  • 
    
• 44. In the class TopDownMergeSortTest, create a static method named sortTest that will perform and print the result of a single test for the method sort from TopDownMergeSort 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.
  • Hint:
• 45. In the class TopDownMergeSortTest, create a static method named sortAllTests that will perform all the tests for sort method from class TopDownMergeSort. 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.
  • Hint:
• 46. In the class TopDownMergeSortTest, create the main method and call the previous method. Check your resullts. Test and debug until your examples work well. Include a text with the obtained correct results in your PDF submission.
  • Hint 1:
  • Hint 2:

Task 5 Experimental Time Analysis

• 51. In the “a041” package, create a public class named TopDownMergeSortAnalysis
• 52. In the class TopDownMergeSortAnalysis create a private static method meanTime (similar with previous mean time methods). It receives the name of the test, number of random executions and the length of the array. It returns a time analysis object containing the time analysis of the performed executions.
  • Hint:
• 53. In the class TopDownMergeSortAnalysis create a private static method, printMeanExecutionTimeGrowthTable. It receives the number of random executions per length, the starting length, the increment from one tested length to the next one and the endding length. It prints the growtth table. Similar with previous growth tables.
  • Hint:
• 54. In the class TopDownMergeSortAnalysis, create the main method and call the previous method. Call for 10 big numbers, that will generate over 10ms execution time. Include a text with the obtained analysis in your PDF submission.
  • Hint 1
  • Hint 2

Task 6: Analyze the execution time and memory needs for the top-down merge sort.

• 61. Explain in your own words which is the theoretical order of growth for the method. Explain why. (1-2 paragraphs)
• 62. Draw a graph for the values obtained in 54.
• 63. Explain if the graph confirms or not the theoretical order of growth above.
• 64. How the graphs compares with the graphs for elementary types of sorts? Is the result expected?
• 65. Analyze the memory needs for this sort method. Are they relevant? Why?

Grading: 0.90 points (see grading rubric for details)

Global Submission Instruction:

• You must follow the instructions described in the folder: “512 All Modules”, subfolder “A00 Global Instructions“, item “Programming Assignment Submission” (if not otherwise specified)

Submission:

• A ZIP file containing all Java files in the package a041 (the package must contain all the code to execute – do not call methods from other packages – except Java predefined packages)
• A PDF file with the new source code that you wrote in tasks 3, 4 and 5 included as text (not screenshots)
• A PDF file with the execution of tasks 35, 46 and 54 included as text (not screenshots)
• A PDF file with the answers for Task 2 and Task 6