利用归并排序算法将读入的n个数从小到大排序后输出。 （C++选手请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。） 本题为函数题，只需要提交函数即可 c/c++： void MergeSort(int[] a,int l,int r) { } java： public static void MergeSort(int[] a,int l,int r) { }

归并排序是一种常见的排序算法，它的核心思想是将一个数组分成两个子数组，分别对子数组进行排序，然后将两个有序的子数组合并成一个有序的数组。下面是一个 C++ 的归并排序实现：

void merge(int a[], int l, int mid, int r) {
    int n1 = mid - l + 1;
    int n2 = r - mid;
    int left[n1], right[n2];
    for (int i = 0; i < n1; i++) {
        left[i] = a[l + i];
    }
    for (int i = 0; i < n2; i++) {
        right[i] = a[mid + 1 + i];
    }
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            a[k++] = left[i++];
        } else {
            a[k++] = right[j++];
        }
    }
    while (i < n1) {
        a[k++] = left[i++];
    }
    while (j < n2) {
        a[k++] = right[j++];
    }
}

void MergeSort(int a[], int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = l + (r - l) / 2;
    MergeSort(a, l, mid);
    MergeSort(a, mid + 1, r);
    merge(a, l, mid, r);
}

在 `merge` 函数中，我们需要先将数组分成两个子数组 `left` 和 `right`，然后将它们按照从小到大的顺序合并成一个有序的数组。在 `MergeSort` 函数中，我们将数组分成两个子数组，分别对它们进行排序，然后再将它们合并起来。递归的基本情况是当子数组的长度为 1 或 0 时，它们已经有序了，无需排序。

下面是一个 Java 的归并排序实现：

public static void merge(int[] a, int l, int mid, int r) {
    int n1 = mid - l + 1;
    int n2 = r - mid;
    int[] left = new int[n1];
    int[] right = new int[n2];
    for (int i = 0; i < n1; i++) {
        left[i] = a[l + i];
    }
    for (int i = 0; i < n2; i++) {
        right[i] = a[mid + 1 + i];
    }
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            a[k++] = left[i++];
        } else {
            a[k++] = right[j++];
        }
    }
    while (i < n1) {
        a[k++] = left[i++];
    }
    while (j < n2) {
        a[k++] = right[j++];
    }
}

public static void MergeSort(int[] a, int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = l + (r - l) / 2;
    MergeSort(a, l, mid);
    MergeSort(a, mid + 1, r);
    merge(a, l, mid, r);
}

同样地，这个算法的时间复杂度是 $O(n\log n)$，其中 $n$ 是数组的长度。