排序之归并与基数：2路归并排序(递归与迭代)、归并排序的应用(外部排序)、基数排序(LSD与MSD)

各位同学，今天我们来啃两块硬骨头——归并排序和基数排序。说实话，这两个家伙在面试和实战中出现的频率非常高。归并排序是分治思想的经典代表，而基数排序则另辟蹊径，用空间换时间。我个人习惯把归并排序比作“整理两堆扑克牌”，把基数排序比作“按位分拣快递”。咱们一个一个来拆解。

一、2路归并排序：递归与迭代

归并排序的核心思想就八个字：先分后合，两两合并。你想想看，如果给你两个已经排好序的数组，让你合并成一个有序数组，是不是很简单？双指针一划拉就完事了。归并排序就是利用这个特性，先把大数组拆成小数组，拆到只有一个元素（天然有序），然后再两两合并回去。

1. 递归实现（自上而下）

递归版本最符合人的直觉。我刚开始学的时候，觉得递归特别绕，后来画了一张图才彻底明白。说白了就是：先递归拆，再回溯合。

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// 递归版归并排序
void mergeSortRecursive(int arr[], int left, int right) {
    if (left >= right) return;  // 只剩一个元素，不用排了
    int mid = left + (right - left) / 2;
    mergeSortRecursive(arr, left, mid);
    mergeSortRecursive(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

2. 迭代实现（自下而上）

迭代版本不用递归，而是用循环控制合并的步长。从长度为1的子数组开始合并，然后长度翻倍，直到整个数组有序。这样写的好处是——没有递归调用，栈空间省下来了。

void mergeSortIterative(int arr[], int n) {
    for (int size = 1; size < n; size *= 2) {
        for (int left = 0; left < n - size; left += 2 * size) {
            int mid = left + size - 1;
            int right = (left + 2 * size - 1 < n - 1) ? 
                         left + 2 * size - 1 : n - 1;
            merge(arr, left, mid, right);
        }
    }
}

嗯，这里要注意边界条件。right 不能越界，所以用了三元表达式做保护。我在项目中调试这个迭代版本时，就踩过数组越界的坑，当时排查了半天才发现是 size 翻倍后 right 计算错了。

二、归并排序的应用：外部排序

外部排序是归并排序最牛的应用场景之一。你想想看，如果数据量大到内存装不下，比如10TB的日志文件，你怎么排序？没法一次性读入内存，那就得用外部排序。

外部排序的核心思路就三步：

1. 分割：把大文件切成若干个小块，每块都能读入内存。
2. 内部排序：对每个小块用快速排序或归并排序排好，写回磁盘。
3. 多路归并：同时打开多个有序小文件，用最小堆或败者树做多路合并，输出到最终文件。

我在做数据库存储引擎时，就遇到过需要排序几十亿条记录的场景。当时用的就是多路归并，每路从磁盘读一个块到内存缓冲区，用败者树选出最小值输出。这里有个关键点——缓冲区大小和归并路数要平衡。路数太多，每次比较的开销大；路数太少，归并趟数多，磁盘I/O次数就多。

三、基数排序：LSD与MSD

基数排序不走寻常路。它不比较元素大小，而是按位分配。我习惯把它想象成“按快递单号分拣包裹”——先按最后一位数字分到10个筐里，再按倒数第二位分，依此类推。

1. LSD（最低位优先）

LSD 从最低位开始，逐位排序。每次排序都用稳定的计数排序（或桶排序）来保证相对顺序不变。举个例子，排序三位数：先按个位排，再按十位排，最后按百位排。排完百位后，整个数组就有序了。

void radixSortLSD(int arr[], int n) {
    int max = getMax(arr, n);
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, n, exp);
    }
}

void countingSortByDigit(int arr[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

2. MSD（最高位优先）

MSD 从最高位开始排。排完最高位后，数据被分成若干组，每组内部再递归按次高位排。MSD 的优点是——如果最高位就能把数据分得很散，那后续的排序量会小很多。但缺点也很明显：递归分组，实现起来比 LSD 复杂。

我个人经验是：如果数据分布均匀，LSD 更简单高效；如果数据有大量重复高位，MSD 能提前剪枝。比如排序身份证号，前几位很多重复的，用 MSD 反而浪费，因为高位分不出多少组。

四、知识体系总览

下面这张图是我自己整理的，把归并排序和基数排序的核心脉络画出来了。你看一眼就能明白它们各自的特点和适用场景。

五、实战对比与选择建议

最后说句掏心窝的话：没有银弹。归并排序稳定、适合外部排序，但需要额外空间；基数排序在特定场景下快得离谱，但适用范围有限。我建议你根据数据特征来选——如果数据是整数且范围不大，试试基数排序；如果是通用场景，归并排序更稳妥。

公众号:蓝海资料掘金营，微信deep3321