一. 题目

二. 思路

三. 代码

import java.io.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

public class Main
{
    static final int N = (int) 1e5 + 10;
    static final ThreadLocalRandom rnd = ThreadLocalRandom.current();
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static String[] rs;

    int n;
    int[] a = new int[N], t = new int[N];

    public static void main(String[] args) throws Exception
    {
        Main main = new Main();
        main.work();
    }

    void mergeSort(int l, int r)
    {
        if (l >= r) return;
        int mid = l + r >> 1;
        mergeSort(l, mid);//处理子
        mergeSort(mid + 1, r);

        int i = l, j = mid + 1, k = 0;//归并左右
        while (i <= mid && j <= r)
            if (a[i] <= a[j]) t[k++] = a[i++];
            else t[k++] = a[j++];
        while (i <= mid) t[k++] = a[i++];
        while (j <= r) t[k++] = a[j++];

        System.arraycopy(t, 0, a, l, k);//赋值回原数组
    }

    void work() throws Exception
    {
        //读入数据
        rs = br.readLine().split(" ");
        n = Integer.parseInt(rs[0]);
        rs = br.readLine().split(" ");
        for (int i = 0; i < n; ++i)
            a[i] = Integer.parseInt(rs[i]);

        mergeSort(0, n - 1);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; ++i)
            sb.append(a[i]).append(" ");
        bw.write(sb.toString());
        bw.close();
    }
}