这是合并排序吗？

Question

我尝试编写 MergeSort 代码。但是我的代码看起来与著名的 MergeSort 实现非常不同。所以我想知道我的实现是否正确。我的算法采用两个 int 数组（每个数组都已排序）并将它们放入一个已排序的大数组中。我的算法的渐近复杂度是多少？非常感谢！！

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 1

您拥有的是合并两个已排序数组的合并（不是合并排序）。时间复杂度为O(n)，其中n为array元素个数+array2元素个数之和。