排序算法之归并排序代码模板（C/C++/Java/Python多版本）

排序算法之归并排序代码模板（C/C++/Java/Python多版本）的重点在于把前置条件、操作顺序和容易误判的地方分清楚。

归并算法是一种典型的分治排序算法，其核心过程是“先分后合”：首先将待排序序列递归地分成最小的子序列（直到每个子序列只包含一个元素），然后将这些有序的子序列两两合并，通过逐次比较、按序排列，最终合并成一个完整的有序序列。整个算法的时间复杂度稳定为 O(n log n)，且具有稳定性，适用于大规模数据的排序。

1. C/C++版代码：

void merge(int *a, int l, int r, int mid) {    // 合并两个有序子数组a[l...mid]和a[mid+1...r]    int temp[r - l + 1], tempnum = 0; // 临时数组存放合并结果    int pos1 = l, pos2 = mid + 1;     // 分别指向两个子数组的起始位置        // 合并两个子数组，取较小者放入临时数组    while (pos1 <= mid && pos2 <= r) {        if (a[pos1] <= a[pos2])             temp[tempnum++] = a[pos1++];        else             temp[tempnum++] = a[pos2++];    }        // 处理剩余元素    while (pos1 <= mid) temp[tempnum++] = a[pos1++];    while (pos2 <= r)   temp[tempnum++] = a[pos2++];        // 将合并结果复制回原数组    for (int i = 0; i < tempnum; i++)         a[l + i] = temp[i];} void merge_sort(int *a, int l, int r) {    // 归并排序主函数：对数组a的[l,r]区间进行升序排序    if (l < r) {                    // 递归终止条件：区间长度大于1        int mid = (l + r) / 2;      // 计算中点，分割区间                // 递归排序左右子区间        merge_sort(a, l, mid);      // 排序左半部分[l,mid]        merge_sort(a, mid + 1, r);  // 排序右半部分[mid+1,r]                // 合并两个已排序的子区间        merge(a, l, r, mid);    }}

2. Java版代码：

public class MergeSort {        private static void merge(int[] a, int l, int r, int mid) {        // 合并两个有序子数组a[l...mid]和a[mid+1...r]        int[] temp = new int[r - l + 1]; // 临时数组存放合并结果        int tempnum = 0;                 // 临时数组索引        int pos1 = l, pos2 = mid + 1;    // 分别指向两个子数组的起始位置                // 合并两个子数组，取较小者放入临时数组        while (pos1 <= mid && pos2 <= r) {            if (a[pos1] <= a[pos2])                 temp[tempnum++] = a[pos1++];            else                 temp[tempnum++] = a[pos2++];        }                // 处理剩余元素        while (pos1 <= mid) temp[tempnum++] = a[pos1++];        while (pos2 <= r)   temp[tempnum++] = a[pos2++];                // 将合并结果复制回原数组        for (int i = 0; i < tempnum; i++)             a[l + i] = temp[i];    }        private static void mergeSort(int[] a, int l, int r) {        // 归并排序主函数：对数组a的[l,r]区间进行升序排序        if (l < r) {                    // 递归终止条件：区间长度大于1            int mid = (l + r) / 2;      // 计算中点，分割区间                        // 递归排序左右子区间            mergeSort(a, l, mid);      // 排序左半部分[l,mid]            mergeSort(a, mid + 1, r);  // 排序右半部分[mid+1,r]                        // 合并两个已排序的子区间            merge(a, l, r, mid);        }    }        // 公共接口方法，隐藏实现细节    public static void sort(int[] array) {        if (array == null || array.length == 0) return;        mergeSort(array, 0, array.length - 1);    }}

3. Python版代码：

def merge(a, l, r, mid):    # 合并两个有序子数组a[l...mid]和a[mid+1...r]    temp = [0] * (r - l + 1)  # 临时数组存放合并结果    tempnum = 0               # 临时数组索引    pos1, pos2 = l, mid + 1   # 分别指向两个子数组的起始位置        # 合并两个子数组，取较小者放入临时数组    while pos1 <= mid and pos2 <= r:        if a[pos1] <= a[pos2]:            temp[tempnum] = a[pos1]            tempnum += 1            pos1 += 1        else:            temp[tempnum] = a[pos2]            tempnum += 1            pos2 += 1        # 处理剩余元素    while pos1 <= mid:        temp[tempnum] = a[pos1]        tempnum += 1        pos1 += 1    while pos2 <= r:        temp[tempnum] = a[pos2]        tempnum += 1        pos2 += 1        # 将合并结果复制回原数组    for i in range(tempnum):        a[l + i] = temp[i]def merge_sort(a, l, r):    # 归并排序主函数：对数组a的[l,r]区间进行升序排序    if l < r:                     # 递归终止条件：区间长度大于1        mid = (l + r) // 2        # 计算中点，分割区间                # 递归排序左右子区间        merge_sort(a, l, mid)     # 排序左半部分[l,mid]        merge_sort(a, mid + 1, r) # 排序右半部分[mid+1,r]                # 合并两个已排序的子区间        merge(a, l, r, mid)