并归排序

• 分治思想：
• 分治以数组的中间点
• 递归排序左边和右边
• 归并（用一个新数组，合二为一）

/**
 * P787 并归排序
 * @author vccyb
 *
 */
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //1. 输入
        int n = Integer.parseInt(br.readLine());
        String[] str = br.readLine().split(" ");
        int[] nums = new int[n];
        for(int i=0;i<n;i++){
            nums[i] = Integer.parseInt(str[i]);
        }

        //2. 调用并归排序算法
        merge_sort(nums, 0, n-1);
        for(int i=0;i<n;i++){
            System.out.print(nums[i]+" ");
        }

    }

    public static void merge_sort(int[] arr, int l, int r){
        if(l>=r) return; //递归结束条件

        //1. 获取分界点，确定的一定是重点,索引哦
        int mid = l + r >> 1;
        //2. 递归
        merge_sort(arr, l, mid);
        merge_sort(arr, mid+1, r);

        //3. 归并
        int[] tmp = new int[r-l+1];
        int i = l; //左边的索引
        int j = mid+1;//右边的索引
        int k = 0; //零时数组的索引

        //每次都将小的过去
        while(i<=mid&&j<=r){
            if(arr[i]<arr[j]){
                tmp[k++]=arr[i++];
            }else{
                tmp[k++]=arr[j++];
            }
        }
        //注意哦，要扫尾巴,两个只会执行其中的一个哦
        while(i<=mid) tmp[k++]=arr[i++];
        while(j<=r) tmp[k++]=arr[j++];

        //放回原数组
        for(i=l,j=0;i<=r;i++,j++){
            arr[i]=tmp[j];
        }

    }

}