// add elements left in the first array
while(i <= mid) {
temp[k] = Arr[i];
k += 1; i += 1;
}
// add elements left in the second array
while(j <= end) {
temp[k] = Arr[j];
k += 1; j += 1;
}
I need help figuring out what the code for a copyArray() function should be. I'm stuck having to follow/implement a particular pseudocode, so I'm unable to use any other code solutions that make more sense. The overall goal is to program a Merge Sort algorithm.
The catch is that apparently I'm unable to use any of the logic from algorithms I've come across searching the net, since none of the merge sort examples out there implement that function inside their sort() or merge() method that are usually part of the merge sort algorithm, and seem to just do what i need the copyArray() function to do in the last few lines of code of most merge() methods examples I've found.
Basically, I must create a copyArray() function that should receive and add an element to a temporary array that will replace the original array.
The copyArray() method should have the following signature/set of arguments/parameters
public void copyArray(int[]arrayTemp, int[] numbers, int start) {
}
I think it should do what basically the code above does, which is found in the last few lines of a usual merge/sort() method part of a typical MergeSort algorithms out there.
My best guess is that the copyArray() function should have a for-loop that iterates over the arrays replacing the elements sorted in the temp array to the original array. But I'm kind of lost now. Does anyone have tips/ideas on how to tweak a typical iteration for loop if that's even how I should be going about it?
Here's the full code I've got so far, but it's not working correctly.
import java.util.Arrays;
public class MergeSortO {
// 1. Start from the mergeSort() method, which splits the array in two, recursively sorts both, and merges the result.
// mergeSort()
/* mergeSort(array, start, end)
if(start < end)
midPoint = (end - start) / 2 + start
mergeSort(array, start, midPoint)
mergeSort(array, midPoint + 1, start)
merge(array, start, midPoint, end)
*/
public void mergeSort(int[] numbers , int start, int end) {
if (start < end) {
int midPoint = (end - start) / 2 + start;
mergeSort(numbers, start, midPoint);
mergeSort(numbers, midPoint +1, start);
merge(numbers, start, midPoint, end); // CALLS merge()
}
}
//2. Then, implement the merge method, which merges both ends of the split array into another space.
/*
merge(array, start, middle, end) // merge()
i = start
j = middle + 1
arrayTemp = initArrayOfSize(end - start + 1)
for (k = 0 until end-start)
if (i <= middle && (j > end || array[i] <= array[j]))
arrayTemp[k] = array[i]
i++
else
arrayTemp[k] = array[j]
j++
copyArray(arrayTemp, array, start)
*/
public void merge(int[] numbers , int start, int middle, int end) { // merge()
int i = start;
int j = middle +1;
int n1 = (end - start + 1);
int[]arrayTemp = new int [n1];
for(int k = 0; k < end - start; k++) {
if ( i <= middle && (j > end || numbers[i] <= numbers[j])) {
arrayTemp[k] = numbers[i];
i++;
}
else {
arrayTemp[k] = numbers[j];
j++;
copyArray(arrayTemp, numbers, start);
}
}
}
/* 3. After the merge is done, copy the new array back in place of the input array.
*/
public void copyArray(int[] arrayTemp, int[] numbers, int start){
int len = arrayTemp.length-1;
for (int i = start; i <= start ; i+=1) {
numbers[i] = arrayTemp[i-start];
}
}
public static void main(String[] args) {
/*
1. Start from the mergeSort() method, which splits the array in two, recursively sorts both, and merges the result.
2. Then, implement the merge method, which merges both ends of the split array into another space.
3. After the merge is done, copy the new array back in place of the input array w/ copyArray().
*/
MergeSortO sort = new MergeSortO();
int[] numbers = new int[]{4,5,33,17,3,21,1,16};
int start = 0;
int end = numbers.length - 1;
int middle = (end - start) / 2 + start;
sort.mergeSort(numbers, start, end);
System.out.println(Arrays.toString(numbers));
}
} ///
Thanks in advance!
