理解归并排序：我的Java实现代码相关技术问询

嘿，刚学完归并排序的教程，我自己写了个Java实现，同时也梳理了下对这个算法的深层理解，分享给大家～

一、完整Java实现代码 #

package com.test.sort;
import java.util.Scanner;

//// 测试用例：100 80 90 70 60 40 50 30 10 20 或者 1 3 5 4 2
public class MergeSortTest {
    private static int[] dataIntAry;

    public static void main(String[] args) {
        System.out.println("Enter data to be sorted : ");
        Scanner scanner = new Scanner(System.in);
        String data = scanner.nextLine();
        String[] dataAry = data.split("\\ ");
        dataIntAry = new int[dataAry.length];
        
        // 将字符串数组转为整数数组
        for (int i = 0; i < dataAry.length; i++) {
            dataIntAry[i] = Integer.parseInt(dataAry[i]);
        }
        
        // 执行归并排序
        mergeSort(0, dataIntAry.length - 1);
        
        // 输出排序结果
        System.out.println("Sorted data:");
        for (int num : dataIntAry) {
            System.out.print(num + " ");
        }
        scanner.close();
    }

    // 归并排序核心：分治拆分
    private static void mergeSort(int left, int right) {
        if (left < right) {
            // 计算中间点，避免left+right溢出
            int mid = left + (right - left) / 2;
            
            // 递归拆分左半部分
            mergeSort(left, mid);
            // 递归拆分右半部分
            mergeSort(mid + 1, right);
            
            // 合并两个有序子数组
            merge(left, mid, right);
        }
    }

    // 合并两个有序子数组
    private static void merge(int left, int mid, int right) {
        // 计算两个子数组的长度
        int n1 = mid - left + 1;
        int n2 = right - mid;
        
        // 创建临时数组存储子数组元素
        int[] leftAry = new int[n1];
        int[] rightAry = new int[n2];
        
        // 复制原数组数据到临时数组
        for (int i = 0; i < n1; i++) {
            leftAry[i] = dataIntAry[left + i];
        }
        for (int j = 0; j < n2; j++) {
            rightAry[j] = dataIntAry[mid + 1 + j];
        }
        
        // 合并临时数组到原数组
        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftAry[i] <= rightAry[j]) {
                dataIntAry[k] = leftAry[i];
                i++;
            } else {
                dataIntAry[k] = rightAry[j];
                j++;
            }
            k++;
        }
        
        // 处理左子数组剩余元素
        while (i < n1) {
            dataIntAry[k] = leftAry[i];
            i++;
            k++;
        }
        
        // 处理右子数组剩余元素
        while (j < n2) {
            dataIntAry[k] = rightAry[j];
            j++;
            k++;
        }
    }
}

二、归并排序核心原理 #

归并排序是分治算法的经典实现，核心逻辑可以拆解为三步：

• 拆分：把未排序的数组不断拆分为左右两个子数组，直到每个子数组仅包含一个元素（单个元素天然有序）。
• 递归排序：对每个子数组递归执行拆分与排序操作。
• 合并：将两个有序的子数组合并为一个更大的有序数组，重复这个过程直到得到完整的有序数组。

三、关键细节与特性解析 #

• 避免整数溢出：计算中间索引时用mid = left + (right - left) / 2，而不是直接(left + right) / 2——当left和right都是较大的整数时，后者会触发整数溢出。
• 空间复杂度：归并排序的空间复杂度是O(n)，因为合并阶段需要额外的临时数组存储子数据，这是它相对于原地排序算法（比如快速排序）的一个差异点。
• 时间复杂度：不管数组初始状态如何，归并排序的最好、最坏、平均时间复杂度都是O(n log n)，因为拆分的层数是log₂n，每层合并的时间开销是O(n)。
• 稳定性：归并排序是稳定排序算法，即相同值的元素在排序后相对位置不会改变，这一点在处理带关联数据的排序场景很有用。

四、测试用例参考 #

可以用这些输入验证代码：

测试输入1：100 80 90 70 60 40 50 30 10 20
预期输出：10 20 30 40 50 60 70 80 90 100

测试输入2：1 3 5 4 2
预期输出：1 2 3 4 5

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