C语言实现归并排序详解：原理、代码与性能分析

// 合并将两个有序序列（[low,mid],[mid+1,high]）合并
void Merge(int arr[], int low, int mid, int high) {
    int i = low, j = mid + 1, p = 0;

    // 动态申请暂存数组
    int *newarr = (int *)malloc((high - low + 1) * sizeof(int));
    if (!newarr) {
        printf("malloc error!\n");
        exit(1);
    }

    // 依次比较并复制较小值
    while (i <= mid && j <= high) {
        if (arr[i] < arr[j])
            newarr[p++] = arr[i++];
        else
            newarr[p++] = arr[j++];
    }

    // 处理剩余元素
    while (i <= mid)
        newarr[p++] = arr[i++];
    while (j <= high)
        newarr[p++] = arr[j++];

    // 将结果复制回原数组
    for (i = low, p = 0; p < (high - low + 1); i++, p++)
        arr[i] = newarr[p];
    free(newarr);
}

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

static void merge1(int array[], int tmp[], int lpos, int rpos, int rend);
static void msort1(int array[], int tmp[], int left, int right);

void merge_sort1(int array[], int n) {
    assert(array != NULL && n > 1);
    
    int *tmp = (int *)malloc(sizeof(int) * n);
    assert(tmp != NULL);
    
    // 备份到tmp，方便后续交替使用
    for (int i = 0; i < n; i++) {
        tmp[i] = array[i];
    }
    
    msort1(array, tmp, 0, n - 1);
    free(tmp);
}

// 递归划分
static void msort1(int array[], int tmp[], int left, int right) {
    assert(array != NULL && tmp != NULL);
    if (left == right)
        return;

    int center = (left + right) / 2;
    // 注意这里的参数传递：先排tmp再copy回array，或者反之
    // 此版本逻辑：msort1将tmp的数据按顺序整理，最终存入array
    msort1(tmp, array, left, center);
    msort1(tmp, array, center + 1, right);
    merge1(tmp, array, left, center + 1, right);
}

// 合并操作
static void merge1(int array[], int tmp[], int lpos, int rpos, int rend) {
    assert(array != NULL && tmp != NULL);
    
    int lend = rpos - 1;
    int tmp_pos = lpos;

    // 核心比较逻辑
    while (lpos <= lend && rpos <= rend) {
        if (array[lpos] <= array[rpos])
            tmp[tmp_pos++] = array[lpos++];
        else
            tmp[tmp_pos++] = array[rpos++];
    }

    // 处理剩余段
    while (lpos <= lend)
        tmp[tmp_pos++] = array[lpos++];
    while (rpos <= rend)
        tmp[tmp_pos++] = array[rpos++];
}

int main(int argc, char *argv[]) {
    int a[7] = {6, 5, 4, 3, 2, 1, 7};
    merge_sort1(a, 7);
    
    for (int i = 0; i < 7; i++) {
        printf("%3d", a[i]);
    }
    printf("\n");
    return 0;
}

/* 自底向上归并排序 */
void MergePass(SeqList R, int length) {
    // 这里假设 SeqList 包含 data 和 length 成员，实际实现需根据具体结构体调整
    // 伪代码逻辑演示：
    int i;
    for (i = 0; i + 2 * length - 1 < n; i += 2 * length)
        Merge(R, i, i + length - 1, i + 2 * length - 1);
    
    // 处理最后剩余的子文件
    if (i + length - 1 < n)
        Merge(R, i, i + length - 1, n - 1);
}

void MergeSort(SeqList R) {
    int length;
    for (length = 1; length < n; length *= 2)
        MergePass(R, length);
}

void merge(int array[], int tmp[], int lpos, int rpos, int rend) {
    int i, leftend, num, tmppos;

    leftend = rpos - 1;
    num = rend - lpos + 1;
    tmppos = lpos;

    while (lpos <= leftend && rpos <= rend) {
        if (array[lpos] <= array[rpos])
            tmp[tmppos++] = array[lpos++];
        else
            tmp[tmppos++] = array[rpos++];
    }

    while (lpos <= leftend)
        tmp[tmppos++] = array[lpos++];
    while (rpos <= rend)
        tmp[tmppos++] = array[rpos++];

    // 从后往前拷贝，避免覆盖未读取的数据
    for (i = 0; i < num; i++, rend--)
        array[rend] = tmp[rend];
}