归并排序

什么是归并排序？

归并排序分为两步：

1. 拆分：将待排序的数组递归地拆分成两个子数组，直到每个子数组只包含一个元素为止。这可以通过不断将数组拆分成左右两半来实现。
2. 合并：将拆分后的子数组两两合并，合并的同时进行排序，得到更大的已排序子数组，直到最终将所有子数组合并成一个完整的有序数组。合并操作会将两个有序的子数组合并成一个有序的大数组。

代码实现

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

void merge(int arr[], int start, int mid, int end)
{
    int* temp = (int*)malloc((end - start + 1) * sizeof(int)); // 开辟动态内存，来存储临时数组
    if (temp == NULL)
    {
        printf("Failed to allocate memory for temp array!");
        return;
    }
    int k = 0; // 临时数组下标
    int i = start; // 左子序列起始位置
    int j = mid + 1; // 右子序列起始位置
    while (i <= mid && j <= end) // 将两个子序列合并成一个有序的序列
    {
        if (arr[i] < arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) // 将左序列剩余部分拷贝进 temp  【i, mid】
    {
        temp[k++] = arr[i++];
    }
    while (j <= end) // 将右序列剩余部分拷贝进 temp  【j, end】
    {
        temp[k++] = arr[j++];
    }
    k = 0;
    while (start <= end) // 将 temp 中存储的有序序列从 start 处开始，按照顺序放回原数组
    {
        arr[start++] = temp[k++];
    }
    free(temp);
}


void merge_sort(int arr[], int start, int end)
{
    if (start < end) // 终止条件：区间内只有一个元素
    {
        int mid = (start + end) / 2; // 分割数组，将其递归分成两个子序列进行排序
        merge_sort(arr, start, mid);
        merge_sort(arr, mid + 1, end);
        merge(arr, start, mid, end); // 将两个有序子序列合并
    }
}

int main()
{
    int arr[] = { 10,9,8,7,6,5,4,3,2,1 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    int start = 0;
    int end = sz - 1;
    merge_sort(arr, start, end);
    for (int i = 0; i < sz; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

输出：
1 2 3 4 5 6 7 8 9 10