KSV97 KSV97 - 11 days ago 5
Java Question

Is this MergeSort?

i tried to code MergeSort. But my Code looks very different than famous implementations of MergeSort. So i'd like to know, if my implementation is correct. My Algorithm takes two int arrays (each is sorted) and puts them into a sorted big array. And whats the asymptotic complexity of my algorithm? Thank you very much!!

public static int[] myMergeSort(int[] array, int[] array2) {
int[] giveback = new int[array.length + array2.length];
int i = 0;
int j = 0;

for (int x = 0; x < giveback.length; x++) {
if (array[i] >= array2[j]){
giveback[x] = array2[j];
j++;
} else {
giveback[x] = array[i];
i++;
}

if (i == array.length) {
x++;
for (int c = j; c < array2.length; c++) {
giveback[x] = array2[c];
x++;
}
return giveback;
}

if (j == array2.length) {
x++;
for (int b = i; b < array.length; b++){
giveback[x] = array[b];
x++;
}
return giveback;
}
}

return giveback;
}

Answer

What you have is a merge (not a merge sort) that merges two already sorted arrays. Time complexity is O(n), where n is the sum of the number of elements in array + number of elements in array2.