如何判断程序是否运行快速、内存高效且时间复杂度低？

没问题，我来帮你拆解下你的归并排序实现的内存效率、运行速度和时间复杂度~

归并排序的核心是分治思想，每次将数组拆分为两个子数组递归排序，再合并结果。不管是最好、最坏还是平均场景，它的时间复杂度都是O(n log n)——这是这种排序算法的固有特性，只要你的递归拆分和合并逻辑没有写错，这个复杂度是完全有保障的。唯一需要注意的是递归栈深度：如果处理的数组规模极大，可能会触发栈溢出，但从你提到的100行代码的规模来看，完全不用担心这个问题。

从你给出的代码片段来看，每次执行合并操作时都会创建temp1[]和temp2[]两个临时数组，这是标准归并排序的实现方式，对应的辅助空间复杂度是O(n)——因为递归过程中，所有临时数组的总大小最多等于原数组的长度n（递归到最底层时每个临时数组仅存1个元素，向上合并时总规模始终维持在n左右）。

不过这里有个可以优化的点：

• 不要在每次合并时都创建新的临时数组，而是提前初始化一个大小为n的全局临时数组（或者作为参数传入方法），在合并阶段复用它。这样能减少数组创建与销毁的开销，降低GC的压力，尤其在递归次数较多时效果更明显。
• 如果追求极致内存占用，可以尝试原地归并排序，但这种实现难度高，且会因为大量元素移动操作牺牲部分运行速度，对于大多数业务场景来说，标准的O(n)辅助空间实现已经足够高效。

• 小规模子数组切换排序算法：当递归拆分到子数组长度很小（比如小于10）时，直接改用插入排序。插入排序在小规模数据上的常数项开销更小，比递归调用归并排序更快。
• 避免包装类型的拆装箱开销：你代码里用的是Integer[]，如果业务场景不需要包装类型，换成int[]能减少自动拆箱装箱的额外消耗，提升运行速度。
• 跳过无需合并的场景：合并前先判断左半部分的最后一个元素是否小于等于右半部分的第一个元素，如果是，说明两个子数组本身已经有序，直接跳过合并操作，减少不必要的比较和元素复制。

附上你提供的代码片段：

import java.util.*; 
public class Question6 { 
    static void mergeSort(Integer arr1[], int o, int k, int x) { 
        int num1 = k - o + 1; 
        int num2 = x - k; 
        int temp1[] = new int[num1]; 
        // 剩余代码...
    }
}

内容的提问来源于stack exchange，提问作者Redent