Three Things on Format Include a header at the top of you source code that inclu
ID: 3541415 • Letter: T
Question
Three Things on Format
Include a header at the top of you source code that includes the lab #, your name, date, problem description etc.
When naming the file use you username and the lab number For example: jsmithLab1.java
Your code is going to be read make sure to format it correctly (i.e. indent all blocks)
Lecture 2: Chapter 8 Programming Exercise 18 No PLTL
See book as formating of algorithum is not shown well
18. Merge Sort
Write a recursive method mergeSort(int[] a, int start, int finish) that sorts an array of
integers a from index start through index finish. Test your method with an array test
of 100 random numbers.
The algorithm works as follows:
Sort the first half of the array recursively.
Sort the last half recursively.
Merge the two sorted halves together.
Merging is accomplished via a method
int[] merge(a, start, finish),
which returns an array with the two sorted halves of a merged into a single sorted array.
This new array must be copied back to a.
Hint : To merge the two halves:
Create a new temporary array b
leftpointer = start; // leftpointer traverses the left half of the array.
halfway = (start + finish)/2 ;
rightpointer = halfway, // rightpointer traverses the right half, and
bpointer = 0; // bpointer traverses the new array b[].
while ( ( leftpointer <= halfway ) AND (rightpointer <= finish) ) {
if ( a[leftpointer] < a[rightpointer] ) {
b[bpointer] = a[leftpointer] ;
leftpointer++;
} else {
b[bpointer] = a[rightpointer];
rightpointer++;
}
bpointer++;
}
if (leftpointer > halfway) {
// copy the remainder of the right half of a to b
}
if (rightpointer > finish) {
// copy the remainder of the left half of a to b
}
return b or copy back to a
Explanation / Answer
void mergeSort(int[] a, int start, int finish){
if(start < finish){
int halfway = (start+finish)/2;
mergeSort(a,start,halfway);
mergeSort(a,halfway+1,finish);
merge(a,start,finish);
}
}
int[] merge(int[] a,int start,int finish){
int b[];
int halfway = (start+finish)/2;
int leftpointer = start;
int rightpointer = halfway;
int bpointer = 0;
while((leftpointer <= halfway ) AND (rightpointer <= finish)){
if(a[leftpointer] < a[rightpointer]){
b[bpointer] = a[leftpointer] ;
leftpointer++;
}
else{
b[bpointer] = a[rightpointer];
rightpointer++;
}
bpointer++;
}
if(leftpointer > halfway){
while(leftpointer > halfway){ // copy the remainder of the right half of a to b
b[bpointer] = a[leftpointer];
leftpointer++;
bpointer++;
}
}
if(rightpointer > finish){
while(rightpointer > halfway){ // copy the remainder of the left half of a to b
b[bpointer] = a[rightpointer];
rightpointer++;
bpointer++;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.