归并排序简介【算法 11】

归并排序简介

归并排序（Merge Sort）是一种有效的、稳定的、基于分治法的排序算法。它的核心思想是将数组分成更小的部分，分别进行排序后再合并。归并排序具有 (O(n \log n)) 的时间复杂度，在处理大规模数据时表现优异。

算法原理

归并排序的工作原理基于“分治法”（Divide and Conquer），即：

1. 分解（Divide）：将未排序的数组一分为二，直到每个子数组仅包含一个元素。
2. 合并（Conquer）：将两个有序的子数组合并成一个有序数组。

具体步骤如下：

1. 将数组从中间划分为两个子数组。
2. 对两个子数组分别进行归并排序。
3. 合并两个有序的子数组。

归并过程详解

合并两个有序数组的步骤如下：

1. 创建一个临时数组 temp，用于存储合并后的数组。
2. 使用两个指针分别指向两个子数组的起始位置，比较这两个位置上的元素，将较小的元素放入 temp，指针后移。
3. 重复上述操作，直到某一个子数组遍历完成。
4. 将未遍历完的子数组剩余元素直接放入 temp。

算法实现

以下是 C 语言中归并排序的实现代码：

#include <stdio.h>

// 合并两个有序数组
void merge(int arr[], int left, int mid, int right) {
   
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int leftArr[n1], rightArr[n2];
    
    // 分别拷贝左右子数组
    for (int i = 0; i < n1; i++)