BS. 2路归并排序

### 归并排序算法概述

归并排序是一种基于分治法的高效稳定排序算法。该算法的核心思想是将待排序数组分成若干子数组，分别对各子数组进行排序；随后再按照一定顺序合并已排序好的子数组，最终得到完全有序的数据集合。

#### 原理描述

具体来说，在执行2路归并排序时：

- 将原始列表不断分割成较小的部分直到每个部分只含有单个元素；
- 对于每一对相邻的小段落实施两两比较，并按升序重新排列组合起来；
- 反复上述过程直至整个数据集被整理完毕[^1]。

此方法能够确保即使存在重复项也能保持原有的相对位置不变，因此具有稳定性这一重要特性。

#### C语言实现示例

以下是采用C语言编写的简单版本的2路归并排序函数：

#include <stdio.h>
#define MAX 100

void merge(int a[], int low, int mid, int high);
void mergesort(int a[], int low, int high);

int main() {
    int i;
    int array[MAX];
    
    printf("Enter number of elements:");
    scanf("%d", &i); // 输入元素数量
    
    for (int j = 0; j < i; ++j){
        scanf("%d",&array[j]); // 用户输入数值
    }
    
    mergesort(array, 0, i - 1);
    
    printf("\nSorted list is:\n");
    for (int k = 0; k < i ;++k)
       printf("%d ", array[k]);
       
    return 0;
}

// 合并两个已经排好序的区间
void merge(int a[], int low, int mid, int high) {
    int b[MAX], h, i, j, k;
    h = low;
    i = low;
    j = mid + 1;

    while ((h <= mid) && (j <= high)) {
        if (a[h] <= a[j]) {
            b[i] = a[h];
            h++;
        } else {
            b[i] = a[j];
            j++;
        }
        i++;
    }

    if (h > mid) { // 处理剩余未处理过的右半边
        for (k = j; k <= high; k++) {
            b[i] = a[k];
            i++;
        }
    } else {      // 或者左半边
        for (k = h; k <= mid; k++) {
            b[i] = a[k];
            i++;
        }
    }

    for (k = low; k <= high; k++)
        a[k] = b[k]; // 把临时数组b中的值复制回原数组a中
}

// 主要递归调用函数来完成排序工作
void mergesort(int a[], int low, int high) {
    int mid;
    if (low < high) {
        mid=(low+high)/2;
        mergesort(a,low,mid);
        mergesort(a,mid+1,high);
        merge(a,low,mid,high);
    }
}

这段代码展示了如何利用辅助空间`b[]`来进行实际的合并操作以及通过递归来分解问题规模的过程[^2]。