【每日打卡】2021-12-30 第51天 about leetcoderank HOT 18 OPEN

package acwing.sort;
import java.io.IOException;
import java.util.Scanner;

/**
 * @author FuYouJ
 * @date 2021/12/29
 * @desc
 */
public class MergeSort {
    static int[] arr;
    static int[] temp;
    public static void main(String[] args) throws IOException {
        Scanner in =  new Scanner(System.in);
        int n = in.nextInt();
        arr = new int[n];
        temp = 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] + " ");
        }
    }

    private static void mergeSort(final int[] arr) {
        mergeSort(arr,0,arr.length-1);
    }
    private static void mergeSort(final int[] arr, int l, int r){
        if (l >= r){
            return;
        }
        int mid = l + r >> 1;
        mergeSort(arr,l,mid);
        mergeSort(arr,mid + 1,r);
        int k = 0, 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++];
        }
        k = 0;
        for (int index = l; index <= r ; index++) {
            arr[index] = temp[k++];
        }
    }
}