排序算法之归并排序代码模板（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)