题目：

核心思路：归并排序的基本思想是先将n[0..n-1］看成n个长度为1的有序表，将相邻的k(k≥2)个有序子表成对归并，得到n/k个长度为k的有序子表；然后将这些有序子表继续归并，得到n/(k^2)个长度为k^2的有序子表，如此反复进行下去，最后得到一个长度为n的有序表。由于整个排序结果放在一个数组中，所以不需要特别地进行合并操作。
        k=2时每次归并两个相邻的有序子表，称为二路归并排序。若k>2，即归并操作在相邻的多个有序子表中进行，则叫多路归并排序。这里仅讨论二路归并排序算法。
        采用递归实现二路归并排序算法，属于典型的二分法算法。设归并排序的当前区是n[low..high]，其分治策略如下。
        ①分解：将当前序列n[low..high］一分为二，即求mid=(low+high)/2，分解为两个子序列n[low..mid］和n[mid+1..high]（前者的元素个数≥后者的元素个数）。
        ②子问题求解：递归地对两个相邻子序列n[low..mid］和n[mid+1..high］二路归并排序。其终止条件是子序列长度为1或者为0（只有一个元素的子序列或者空表可以看成有序表）。
        ③合并：与分解过程相反，将已排序的两个子序列n[low..mid]（有序段1）和n[mid+1..high]（有序段2）归并为一个有序序列n[low..high]。
        对应的递归二路归并排序算法如下：

import java.util.Scanner;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int x[] = new int[n];
        for (int i = 0;i<x.length;i++){
            x[i] = scanner.nextInt();
        }
        MergeSort1(x,0,x.length-1);
        for (int i = 0;i<x.length;i++){
            System.out.print(x[i]+ " ");
        }
        scan.close();
    }
    public static void Merge(int n[],int low,int mid,int high){//归并两个相邻有序子序列
        ArrayList<Integer> arrayList = new ArrayList<>();//arraylist用作临时表
        int i = low,j = mid+1;//i、j分别为两个子表的下标
        while (i<=mid&&j<=high){//在子表1和子表2均未遍历完时循坏
            if (n[i]<=n[j]){//将子表1中的元素归并到arraylist
                arrayList.add(n[i++]);
            }else {//将子表2中的元素归并到arraylist
                arrayList.add(n[j++]);
            }
        }
        while (i<=mid){//将子表1余下的元素改变到arraylist
            arrayList.add(n[i++]);
        }
        while (j<=high){//将子表2余下的元素改变到arraylist
            arrayList.add(n[j++]);
        }
        i = low;//将arraylist复制回n中
        for (int x : arrayList){
            n[i++] = x;
        }
    }
    public static void MergeSort1(int n[],int low,int high){
        if (low<high){//子序列有两个或两个以上元素
            int mid = (low + high)/2;//取中间位置
            MergeSort1(n,low,mid);//对n[low...mid]子序列排序
            MergeSort1(n,mid+1,high);//对n[mid+1...high]子序列排序
            Merge(n,low,mid,high);//将两个有序子序列合并
        }
    }
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        mergeSort(arr, 0, arr.length - 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) { // 递归终止条件
            int mid = left + (right - left) / 2; // 计算中间索引
            mergeSort(arr, left, mid); // 递归排序左半部分
            mergeSort(arr, mid + 1, right); // 递归排序右半部分
            merge(arr, left, mid, right); // 合并两个有序部分
        }
    }

    // 合并两个有序数组的方法
    public static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1; // 左半部分的长度
        int n2 = right - mid; // 右半部分的长度

        // 创建临时数组存储左右两部分
        int[] L = new int[n1];
        int[] R = new int[n2];

        // 复制数据到临时数组
        for (int i = 0; i < n1; i++) {
            L[i] = arr[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[mid + 1 + j];
        }

        // 合并两个临时数组
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // 复制剩余的元素（如果有的话）
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
}