给定你一个长度为 n的整数数列。

请你使用归并排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n个整数（所有整数均在 1∼范围内），表示整个数列。

输出格式

输出共一行，包含 n个整数，表示排好序的数列。

数据范围

1≤n≤100000

输入样例：

5

3 1 2 4 5

输出样例：

1 2 3 4 5 

 一.归并排序

归并属于分治算法，归并排序的基本思想是将数组分成较小的子数组，递归地对这些子数组进行排序，然后将它们合并在一起，产生最终的有序数组。

举个例子

假设我们要对一个数组[5,3,2,1]进行归并排序，具体步骤如下：

将数组划分为左右两个子数组：[5,3]和[2,1]

对左右两个子数组分别进行归并排序。这里以左边的子数组为例，右边的子数组同理。将左边的子数组[5,3],再次划分为左右两个子数组：[5]和[3]

递归到最下面一层的时候只有一个元素，这个时候递归满足结束条件，会自动return到上一层，而倒数第二层这个时候有从倒数第一层递归回来的两个元素，这个时候这两个元素就会执行接下来的一大串排序指令：

\\此时[5]的索引是0，[3]的索引是1，mid=0,l=0,r=1
int k = 0, i = l, j = mid + 1;
\\i=0,j=1
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k++] = q[i++ ];
else tmp[k++] = q[j++];
\\此时tmp[0]=q[j]=3,j=2,k=1右边的数组没有剩余，左边有剩余q[i]=5
while (i <= mid) tmp[k++] = q[i++];\\成立，tmp[1]=5,k=2,i=1
while (j <= r) tmp[k++] = q[j++];\\不成立
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];\\将临时数组tmp中的有序数组按索引传给
q[N]；

这也是i=l,不能是 i=0的原因

将左右两个子数组[5]和[3]进行归并，得到有序的子数组[3,5],右边的子数组同理.

得到的左右两个有序子数组[3,5]和[1,2]。
进行归并同上，得到有序的子数组[1,2,3,5]。

c++
 

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, q[N], tmp[N];

void mergesort(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    //分
    mergesort(l, mid);
    mergesort(mid + 1, r);
    //治（合并）
    //tmp数组临时存放我们合并的有序序列
    //i是第一个序列的头，j是第二个序列的头
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        //找小的存进tmp中
        if (q[i] <= q[j]) tmp[k ++] = q[i ++];
        else tmp[k ++] = q[j ++];
    }
    //如果还剩下有没放进tmp中的，就按顺序插入tmp的末尾
    //这两个循环最多只会执行一个
    while (i <= mid) tmp[k ++] = q[i ++];
    while (j <= r) tmp[k ++] = q[j ++];
    //再把tmp中的数据copy会原数组里
    for (int i = l, j = 0; i <= r; i ++, j ++)
        q[i] = tmp[j];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++)
        cin >> q[i];
    mergesort(0, n - 1);
    for (int i = 0; i < n; i ++)
        cout << q[i] << " ";
    return 0;
}

java

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i < arr.length;i++){
            arr[i] = s.nextInt();
        }
        mergeSort(arr,0,n-1);
        for(int i = 0;i < arr.length;i++){
            System.out.print(arr[i] + " ");
        }
    }

    public static void mergeSort(int[] arr,int left,int right){
        if(left >= right) return;

        int mid = (left + right) / 2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid + 1,right);

        int[] temp = new int[right - left + 1];
        int k = 0,i = left,j = mid + 1;
        while(i <= mid && j <= right)
            if(arr[i] <= arr[j])
                temp[k ++ ] = arr[i ++ ];
            else
                temp[k ++ ] = arr[j ++ ];

        while(i <= mid)
            temp[k ++ ] = arr[i ++ ];
        while(j <= right)
            temp[k ++ ] = arr[j ++ ];

        for(i = left,j = 0;i <= right;i++,j++)
            arr[i] = temp[j];

    }
}