This week you will complete some exercises involving recursion and sorting which introduce two classic sorting algorithms. It is unlikely that you will complete the entire exercise in the lab.
Here are the files you will be using for this exercise:
And here is the API:The sorting method mergeSort(int[] A) depends on the recursive helper method mergeSort(int[] A, int l, int r, int[] temp), which, in turn, depends on merge(int[] A, int l, int m, int r, int[] temp) (which you were supposed to write in programming exercise 5).
X.class contains a completed version of merge(int[] A, int l, int m, int r, int[] temp). First use X.merge(...) to complete and test mergeSort(int[] A, int l, int r, int[] temp) and then complete and test mergeSort(int[] A). Only after you have completed that, and the quickSort method (see below) should you go back and complete the merge method and use it in mergeSort - being sure to test again.
The sorting method quickSort(int[] A) depends on the recursive helper method quickSort(int[] A, int l, int r), which, in turn, depends on partition(int[] A, int l, int r).
X.class contains a completed version of partition(int[] A, int l, int r). First use X.partition( ... ) to complete and test quickSort(int[] A, int l, int r) and then complete and test quickSort(int[] A). Only after you have completed that, and the mergeSort method (see above) should you go back and complete the partition method and use it in quickSort - being sure to test again.
Sorting.java also contains a method to return a string version of an int array, and there is a Tester.java class that should help you test your methods. Uncomment the part you want to use, or change it if you like.
You can submit this program using the following commend:
% submit 1030 Exercise7 Sorting.java