这是一个稍微简单一点的版本。它仍然具有相同的二次时间复杂度o（n*m），但执行速度比发布的代码快10倍，因此它确实符合优化版本的要求：

class Solution {
    public void merge_chqrlie(int arr1[], int arr2[], int n, int m) {
        if (n > 0 && m > 0) {
            // for each element of arr2
            for (int i1 = 0, i2 = 0, j, k = 0; k < m; k++) {
                // shift it left inside arr2
                for (j = k; j > i2 && arr2[j-1] > arr2[j]; j--) {
                    int temp = arr2[j-1];
                    arr2[j-1] = arr2[j];
                    arr2[j] = temp;
                }
                // if it moved to arr2[0] and is smaller than the last element of arr1
                if (j == 0 && arr1[n-1] > arr2[0]) {
                    // move it to arr1[n-1]
                    int temp = arr1[n-1];
                    arr1[n-1] = arr2[0];
                    arr2[0] = temp;
                    // and further shift it into arr1
                    for (j = n - 1; j > i1 && arr1[j-1] > arr1[j]; j--) {
                        temp = arr1[j-1];
                        arr1[j-1] = arr1[j];
                        arr1[j] = temp;
                    }
                    // update i1: the finalized portion of arr1
                    i1 = j + 1;
                } else {
                    // update i2: the finalized portion of arr2
                    i2 = j + 1;
                }
            }
        }
    }
}

不使用额外空间的合并是一个非常严格的约束：您是否认为局部变量是额外空间？如果允许有限的额外空间（例如128个元素的单个数组），则可以找到更快的解决方案，对于中等大小的数组（超过5000个元素），其执行速度比发布的代码快500到2000倍，但对于大型数组，其时间复杂度仍然是二次的。
这是一个高级解决方案（对于500k元素的阵列，速度提高了1000倍）：

class Solution {
    static int tmp_size = 128;
    static int *tmp;
    public void merge_chqrlie2(int arr1[], int arr2[], int n, int m) {
        if (!tmp)
            tmp = new int[tmp_size];
        for (int chunk = tmp_size; n > 0; n -= chunk, arr1 += chunk) {
            int i = 0, j = 0, k = 0;
            if (chunk > n)
                chunk = n;
            for (k = 0; k < chunk; k++)
                tmp[k] = arr1[k];

            for (k = 0; k < chunk; k++) {
                if (j >= m || tmp[i] <= arr2[j])
                    arr1[k] = tmp[i++];
                else
                    arr1[k] = arr2[j++];
            }
            for (k = 0; i < chunk; k++) {
                if (j >= m || tmp[i] <= arr2[j])
                    arr2[k] = tmp[i++];
                else
                    arr2[k] = arr2[j++];
            }
        }
    }
}

临时存储将以c或c++等语言在堆栈（自动存储）上分配，以获得最佳效率。
这是一个更有效的方法，在病理样本上的性能更好，在随机内容上的速度快2.5倍：

void merge_chqrlie3(int arr1[], int arr2[], size_t n, size_t m) {
    int tmp[128];
    size_t i2 = 0;

    for (size_t chunk = sizeof(tmp) / sizeof(*tmp); n > 0; n -= chunk, arr1 += chunk) {
        size_t i = 0, j = 0, k = 0;

        if (i2 == 0) {
            while (n > 0 && arr1[0] <= arr2[0]) {
                arr1++;
                n--;
            }
        }
        if (chunk > n)
            chunk = n;

        for (k = 0; k < chunk; k++)
            tmp[k] = arr1[k];

        if (chunk <= i2) {
            for (j = 0; j < chunk; j++)
                arr1[j] = arr2[j];
            for (k = 0; j < i2; k++)
                arr2[k] = arr2[j++];
        } else {
            for (k = 0; j < i2; k++)
                arr1[k] = arr2[j++];
            for (; k < chunk; k++) {
                if (j >= m || tmp[i] <= arr2[j])
                    arr1[k] = tmp[i++];
                else
                    arr1[k] = arr2[j++];
            }
            k = 0;
        }
        for (; i < chunk; k++) {
            if (j >= m || tmp[i] <= arr2[j])
                arr2[k] = tmp[i++];
            else
                arr2[k] = arr2[j++];
        }
        i2 = k;
    }
}

减小临时存储大小几乎线性地减慢执行时间： merge_chrlie2 仍然比使用12个元素的本地数组发布的代码快100倍，这很难被视为额外存储。
我在c中运行了一个基准测试，使用无空间合并函数作为经典的自顶向下递归合并排序的合并阶段。以下是包含128个元素的临时数组的计时（*）：

size        malloc      chqrlie3      chqrlie2       chqrlie        shivam
        1000         0.059         0.064         0.064         0.252         2.010
        2000         0.153         0.124         0.126         0.836         7.872
        5000         0.441         0.505         0.528         5.218        49.947
       10000         0.667         0.769         0.898        19.850       205.316
       20000         1.531         1.917         2.195        85.185       812.061
       50000         4.036         6.123         9.244       524.873      5197.808
      100000         8.281        15.466        28.787      2064.165     20485.584
      200000        18.030        51.438       106.391      8342.140     82226.825
      500000        49.201       246.224       557.470     51982.830    511418.600
     1000000       112.594       915.575      2171.953    207096.552   2053797.858
     2000000       215.045      3883.104      8476.783    829806.868   8153974.589
     5000000       565.701     34142.299     67304.217   5855744.544  51565024.699

以下是仅包含5个元素的临时数组的计时：

size        malloc      chqrlie3      chqrlie2       chqrlie        shivam
        1000         0.055         0.089         0.111         0.230         1.963
        2000         0.165         0.247         0.327         0.880         7.891
        5000         0.438         1.309         1.914         4.971        50.376
       10000         0.799         2.832         5.675        21.544       202.929
       20000         1.589         9.265        23.528        82.582       826.768
       50000         4.150        53.408       131.302       519.007      5089.592
      100000         8.375       205.644       533.308      2016.670     20431.584
      200000        17.291       797.865      2193.575      9536.996     82308.875
      500000        61.955      6565.826     15626.427     50813.910    508269.938
     1000000       105.836     21146.977     52530.060    205640.244   2036022.030

（*）计时（毫秒），外推 chqrlie 以及 shivam 分别适用于大于50k和200k的阵列。

因为不能使用任何额外的空间，所以可以同时对这两个数组实现一种选择排序 n + m ，检查每个索引是否已在第二个数组中：

public static void main(String[] args) {
    int[] arr1 = {1, 3, 5, 7};
    int[] arr2 = {0, 2, 6, 8, 9};

    selectionSort(arr1, arr2);

    System.out.println(Arrays.toString(arr1)); // [0, 1, 2, 3]
    System.out.println(Arrays.toString(arr2)); // [5, 6, 7, 8, 9]
}

public static void selectionSort(int[] arr1, int[] arr2) {
    int n = arr1.length;
    int m = arr2.length;
    for (int i = 0; i < n + m; i++) {
        int min = i < n ? arr1[i] : arr2[i - n];
        int min_i = i;
        for (int j = i + 1; j < n + m; j++)
            if (j < n ? arr1[j] < min : arr2[j - n] < min) {
                min = j < n ? arr1[j] : arr2[j - n];
                min_i = j;
            }
        if (i != min_i)
            if (i < n) {
                int temp = arr1[i];
                if (min_i < n) {
                    arr1[i] = arr1[min_i];
                    arr1[min_i] = temp;
                } else {
                    arr1[i] = arr2[min_i - n];
                    arr2[min_i - n] = temp;
                }
            } else {
                int temp = arr2[i - n];
                if (min_i < n) {
                    arr2[i - n] = arr1[min_i];
                    arr1[min_i] = temp;
                } else {
                    arr2[i - n] = arr2[min_i - n];
                    arr2[min_i - n] = temp;
                }
            }
    }
}

另请参见：java选择排序