合并排序

合并排序（Merge Sort）是一种分治算法，通过将原问题划分为若干子问题，递归求解子问题，最后将子问题的结果合并得到原问题的解。具体来说，合并排序的实现步骤如下：

分解：将待排序的n个元素分成两个长度为n/2的子序列，对这两个子序列进行合并排序（递归）。

合并：将两个已经排好序的子序列合并成一个有序序列。

对于长度为n的序列，其最差时间复杂度为O(nlogn)，最优时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)，空间复杂度为O(n)。

以下是合并排序的C语言实现：

#include <stdio.h>

// 合并函数，将两个有序数组合并成一个有序数组
void merge(int arr[], int left[], int leftLen, int right[], int rightLen) {
    int i, j, k;
    i = j = k = 0;

    // 比较两个数组中的元素，将较小的元素放入结果数组中
    while (i < leftLen && j < rightLen) {
        if (left[i] < right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }

    // 将剩余的元素加入结果数组
    while (i < leftLen) {
        arr[k++] = left[i++];
    }
    while (j < rightLen) {
        arr[k++] = right[j++];
    }
}

// 归并排序函数
void mergeSort(int arr[], int len) {
    if (len < 2) {
        return;
    }

    int mid = len / 2;
    int left[mid], right[len - mid];
    int i;

    // 将数组分为左右两个子数组
    for (i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    for (i = mid; i < len; i++) {
        right[i - mid] = arr[i];
    }

    // 对左右两个子数组进行递归排序
    mergeSort(left, mid);
    mergeSort(right, len - mid);

    // 合并两个有序数组
    merge(arr, left, mid, right, len - mid);
}

int main() {
    int arr[] = {4, 2, 1, 7, 5, 8, 3, 6};
    int len = sizeof(arr) / sizeof(arr[0]);
    int i;

    printf("Original array: ");
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    mergeSort(arr, len);

    printf("Sorted array: ");
    for (i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

该实现采用了递归算法，将数组不断分为左右两个子数组，直到子数组的长度小于2，然后对左右两个子数组进行合并排序，最后合并得到有序数组。合并函数采用双指针法，比较两个数组中的元素，将较小的元素放入结果数组中。