时间复杂度

O(nlogn)

JAVA 代码

import java.util.Scanner;
import java.io.BufferedInputStream;

public class Main {
    //程序入口
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        MergeSort(arr, 0, n - 1);

        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
    public static void MergeSort(int[] arr, int l, int r){
        if(l >= r)
            return;
        //0. 确定分界点---取中点
        int mid = l + r >> 1;
        //1. 递归排序左边和右边
            MergeSort(arr, l, mid);
            MergeSort(arr, mid + 1, r);
        //2. 归并---将两个有序数组合并成一个有序数组---双指针算法
        //对两个数组分别取头指针，不断比较两个指针大小，在开辟一个新数组容纳
        int[] temp = new int[r - l + 1];
        int k = 0;//表示当前temp一共有多少个数
        int i = l,j = mid + 1 ;//两个指针
        while(i <= mid && j <= r){
            if(arr[i] <= arr[j])
                temp[k++] = arr[i++];
            else
                temp[k++] = arr[j++];
        }
        while(i <= mid)
            temp[k++] = arr[i++];
        while(j <= r)
            temp[k++] = arr[j++];
        for (i = l, j = 0; i <= r; i++, j++)
            arr[i] = temp[j];
    }
}