题解 | #归并排序

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        scanner.useDelimiter("\n");
        while (scanner.hasNextInt()) {
            int i = scanner.nextInt();
            String S = scanner.next();
            String[] s = S.split(" ");
            int sort = scanner.nextInt();
            int[] original = new int[s.length];
            for (int j = 0; j < s.length; j++) {
                original[j] = Integer.parseInt(s[j]);
            }
            sort2(original, 0, original.length-1, sort);
            for (int s1 : original) {
                System.out.print(s1 + " ");
            }
            System.out.println();
        }
        
    }

    /**
     * 归并排序，第三次写
     * @param args
     */
    public static void sort2(int[] nums, int left, int right, int sort) {
        if (left>=right) return;
        int mid = left+((right-left)>>1);
        sort2(nums, left, mid, sort);
        sort2(nums, mid+1, right, sort);
        merge2(nums, left, mid, right, sort);
    }


     public static void merge2(int[] nums, int left, int mid, int right, int sort) {
        int[] copy = new int[nums.length];
        System.arraycopy(nums, 0, copy, 0, nums.length);

        int k = left,i=left,j=mid+1;
        while (k<=right){
            if (i>mid){
                nums[k++]=copy[j++];
            } else if (j>right){
                nums[k++]=copy[i++];
            } else if (sort==0){
                if (copy[i]>copy[j]) {
                    nums[k++]=copy[j++];
                } else {
                    nums[k++]=copy[i++];
                }
            }  else if (sort==1){
                if (copy[i]<copy[j]) {
                    nums[k++]=copy[j++];
                } else {
                    nums[k++]=copy[i++];
                }
            }
        }
    }
}