始.归并排序的简单介绍

归并排序（Merge Sort）是一种基于分治策略的稳定排序算法，通过递归地将数组分成两半、分别排序后合并，最终实现整体有序。其时间复杂度为 $O(n \log n)$，适合大规模数据排序。

核心思想

1. 分治：将待排序数组不断二分，直到子数组长度为1（天然有序）。
2. 合并：将两个有序子数组合并为一个有序数组，通过比较元素大小按序填充。

算法步骤

分解阶段
递归地将数组从中间分为左右两部分，直到无法再分（子数组长度为1）。

合并阶段

1. 初始化临时数组和左右子数组的起始指针。
2. 比较左右子数组当前指针位置的元素，将较小者放入临时数组，移动对应指针。
3. 将剩余未遍历的元素直接追加到临时数组末尾。
4. 将临时数组拷贝回原数组的对应位置。

复杂度分析

• 时间复杂度：$O(n \log n)$，分解和合并各需 $\log n$ 层，每层合并操作耗时 $O(n)$。
• 空间复杂度：$O(n)$，合并时需要额外临时数组存储数据。

特点

• 稳定性：合并时相同元素保持原序，是稳定排序。
• 适用性：适合链表排序（无需随机访问），但需要额外空间。

一.图文描述流程

合并操作的详细步骤

1. 初始化两个指针分别指向待合并子数组的起始位置。
2. 比较两个指针所指元素的大小，将较小的元素放入临时数组，并移动对应指针。
3. 重复上述比较步骤，直到某一子数组被完全遍历。
4. 将剩余子数组的元素直接追加到临时数组末尾。
5. 将临时数组中的有序数据复制回原数组对应位置。

假设对数组 [9, 7, 8, 6, 4] 进行归并排序：

-----------开始分割(分割顺序是从大到小)

将数组分割为 [9, 7, 8] 和 [6, 4]。

继续分割为 [9, 7]、[8]、[6]、[4]。        -> 此时[8],[6],[4]已分割为最小数组

再将[9, 7]进行分割:  [9]、[7].                ->此时[9],[7],[8],[6],[4]均已被分割为最小

-----------分治结束-------------

-----------开始合并(合并顺序是从小到大)

合并操作：是在将数据组合在一起的同时，对小型数据进行排序并合并

左1:

合并 [9] 和 [7] 得到 [7, 9]。

左2:

合并  [9,  7] 和. [8]. 得到. [7,  8,  9]。

右2:

合并 [4] 和 [6] 得到 [4, 6]。

总:

最后合并. [7,  8,  9]. 和. [4,  6]. 得到. [4,  6,  7,  8,  9]

通过分析以上文字过程，我们可以看出：归并排序是通过递归方式来实现的,先通过递归将每一个元素都拆分开来，当拆分到只有一个元素时开始返回，对从下到上的每一层都进行合并操作，这样就能够得到一个有序的元素数组了.

二.代码实现

以下为归并排序的代码实现:

通过递归来做到对从下往上的每一个子数组都进行归并操作，从而最终使得数组顺序改变。

static int[] merge_arr;

static void merge_sort(int[] arr, int left, int right) {
        //分治
        if(right - left <= 1) return;
        //中间位置 ----> 左侧区间(0 - midLocate) - 右侧区间(midLocate - length)
        int midLocate =  (right + left) / 2;
        merge_sort(arr, left, midLocate);
        merge_sort(arr, midLocate, right);
        //归并操作 - merge
        int[] temp = new int[right-left];    //临时数组
        int index = 0;
        int a = left;
        int b = midLocate;
        while(a < midLocate || b < right){
            if(b == right || (a < midLocate && arr[a] <= arr[b])){
                temp[index++] = arr[a++];
            }else{
                temp[index++] = arr[b++];
            }
        }
        //将临时数组的元素复制到传入数组
        System.arraycopy(temp, 0, arr, left, right - left);
    }

三.性能测试

         接下来,我会分别使用：100个元素的乱序数组，1000个元素的乱序数组，10000个元素的乱序数组以及100000个元素的乱序数组对归并排序进行性能测试

请输入要测试的数组长度(超过10不打印):
100
排序成功!
运行时间:1.0ms

=================================================

请输入要测试的数组长度(超过10不打印):
1000
排序成功!
运行时间:1.0ms

=================================================

请输入要测试的数组长度(超过10不打印):
10000
排序成功!
运行时间:4.0ms

=================================================

请输入要测试的数组长度(超过10不打印):
100000
排序成功!
运行时间:14.0ms

=================================================

请输入要测试的数组长度(超过10不打印):
1000000
排序成功!
运行时间:107.0ms

=================================================

归并排序的理论时间复杂度为O(n log n)。通过测试数据可观察到：

• 数据规模增大10倍时，耗时增长约2-8倍（如1000→10000元素时1ms→4ms），符合对数线性增长趋势
• 百万级数据仍保持百毫秒级处理速度，体现算法高效性

尾.个人想说的话：

我是一名学习JAVA等编程语言的普通学生，如果我的这篇文章帮助到了你，我很开心，同时如果我的文章有问题，请各位发现后对我所说的有问题的部分做出修改和指正（请详细一些），避免他人看到造成误导，欢迎各位在评论区讨论、补充、以及纠正错误。

#如果觉得博客内容对你有帮助的话可以支持一下我的其它博客：

• 上一篇: (Java)算法学习(四): 希尔排序-排序过程拆解与算法优化