reate a program named MergeSort.java then copy the following code to your program: Write a main method that accepts three numbers N, A, B (assume A
- Create a program named MergeSort.java then copy the following code to your program:
- Write a main method that accepts three numbers N, A, B (assume A<B) from the command argument list, then use the number N to create an N-element int array.
public static void mergeSort(int[] arr){
mergeSortRec(arr, 0, arr.length-1);
}
private static void mergeSortRec(int[] arr, int first, int last){
if(first<last){
int mid=(first+last)/2;
mergeSortRec(arr, first, mid);
mergeSortRec(arr, mid+1,last);
merge(arr, first, mid, mid+1, last);
}
}
private static void merge(int[] arr, int leftFirst,
int leftLast, int rightFirst, int rightLast){
int[] aux=new int[arr.length];
//extra space, this is downside of this
int index=leftFirst;
int saveFirst=leftFirst;
while(leftFirst<=leftLast && rightFirst <=rightLast){
if(arr[leftFirst]<=arr[rightFirst]){
aux[index++]=arr[leftFirst++];
}else{
aux[index++]=arr[rightFirst++];
}
}
while(leftFirst<=leftLast){
aux[index++]=arr[leftFirst++];
}
while(rightFirst<=rightLast)
aux[index++]=arr[rightFirst++];
for(index=saveFirst; index<=rightLast; index++)
arr[index]=aux[index];
}
- Assign random numbers between [A, B] to each of the N elements of the array.
- Call mergeSort method to sort the array.
- Write instructions to record the time spent on sorting.
- (Optional) you may write code to verify the array was sorted successfully.
- Once completed, test your program with different numbers N, A, B and screenshot your result. Your result should include the number of elements and sorting time.
- Please include the following in the Word document you created for the assignment for the final submission:
- Copy/paste your completed code in MergeSort.java
- Insert at least one screenshot of the running output in #7 above
- Answer this question: What is the average Big O for this sort?
Step by step
Solved in 3 steps with 3 images
