KSV97 KSV97 - 9 months ago 58
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 Source

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.