结合Insertion Sort与Merge Sort的Java算法是否为原地且稳定排序？

我有一段结合了插入排序和归并排序的Java代码，不确定该组合算法是否属于原地排序（in-place）且稳定排序（stable），希望有人能帮忙解答。

代码实现 #

package org.example;

import java.util.Arrays;

public class Main {
    private static Comparable[] aux;

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    private static void exch(Comparable[] a, int i, int j) {
        Comparable swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    private static void insertionSort(Comparable[] a, int lo, int hi) {
        for (int i = lo; i <= hi; i++) {
            for (int j = i; j > lo && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }

    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        int i = lo, j = mid+1;

        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }

        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        final int INSERTION_SORT_THRESHOLD = 10;
        if (hi <= lo + INSERTION_SORT_THRESHOLD - 1) {
            insertionSort(a, lo, hi);
            return;
        }
        int mid = lo + (hi - lo) / 2;

        sort(a, lo, mid);
        sort(a, mid+1, hi);
        merge(a, lo, mid, hi);
    }

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];
        sort(a, 0, a.length - 1);
    }

    public static void main(String[] args) {
        Integer[] a = {7, 3, 5, 1, 6, 8, 2, 4, 9, 0};
        System.out.println("Before sorting: " + Arrays.toString(a));
        Main.sort(a);
        System.out.println("After sorting: " + Arrays.toString(a));
    }
}

算法特性分析 #

1. 是否为原地排序（in-place）？

不是。
该算法的核心归并步骤依赖全局的aux数组，在sort方法初始化时会创建一个与原数组长度完全相同的辅助数组，额外空间复杂度为O(n)。虽然子数组长度较小时会使用原地的插入排序，但整体算法因为归并阶段的O(n)额外空间，不符合原地排序（要求额外空间复杂度为O(1)，递归栈空间通常不计入）的定义。

2. 是否为稳定排序（stable）？

是。

• 插入排序本身是稳定排序：当元素相等时，less(a[j], a[j-1])返回false，不会触发交换，相等元素的相对顺序得以保留。
• 归并阶段的实现也保证了稳定性：在merge过程中，当aux[j]不小于aux[i]时，会优先选择左侧的aux[i]放入原数组，确保相同元素的相对顺序与原数组一致。
  两个子算法均稳定，且组合过程未破坏稳定性，因此整个算法是稳定的。

内容的提问来源于stack exchange，提问作者Gino.Montaner