用C语言实现由用户输入数组的归并排列

在C语言中，实现数组的归并排序需要分为两个步骤：首先对数组进行分治，然后合并两个有序的部分。以下是简单的归并排序算法步骤及其实现：

1. **分治策略**：
- 将待排序数组一分为二，直到每个子数组只包含一个元素，此时视为已排序。
- 从最小子数组开始，合并相邻的两个子数组。

2. **合并函数**：
- 定义一个辅助函数`merge()`，它接受两个已经排好序的子数组作为参数，合并它们成一个新的有序数组，并返回合并后的数组起始位置。

3. **主函数**：
- 使用递归来调用`mergeSort()`函数对整个数组进行排序。
- `mergeSort()`函数首先检查数组长度是否小于等于1，如果是，则直接返回数组。
- 否则，找到数组中间点，分别对左半部分和右半部分进行排序，然后调用`merge()`函数合并结果。

以下是基本的C语言代码实现：

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

// Merge function to merge two sorted arrays into one
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // Create temporary arrays
    int L[n1], R[n2];

    // Copy data to temp arrays
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    // Merge the temp arrays back into arr[l..r]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged array

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy remaining elements of L[] if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy remaining elements of R[] if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Recursive function to sort an array using merge sort
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Find the middle point
        int m = l + (r - l) / 2;

        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[100], size;
    printf("Enter the number of elements: ");
    scanf("%d", &size);

    printf("Enter the elements:\n");
    for (int i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }

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

    return 0;
}