package suanfa;

import com.algs4.stdlib.StdOut;
/**
 * Created by evan on 16/11/24.
 */
public class mergeSort {

    public static void main(String[] args){

        Integer[] papapa = {1,5,3,5,3,7,5,3,7,9,6,3,2,43,4,43,145,4,33,111};
        sort(papapa,0,papapa.length-1);


        for (Integer value:papapa) {

            StdOut.println(value);
        }

    }

    public static void sort(Comparable[] intList,int low,int high){

        if(low >= high){

            return;
        }
        //开始切分数组
        int mid =low+(high-low)/2;
        sort(intList,low,mid);
        sort(intList,mid+1,high);
        merge(intList,low,high,mid);


    }


    public static void merge(Comparable[] intList,int low,int high,int mid){

        Comparable[] tmp = new Comparable[intList.length];
        int i = low;
        int j = mid+1;
        int start = low;
        while(i<=mid || j<=high){
            //处理边界条件 当有一方到达边界
            if(i>mid){
                tmp[start++] = intList[j++];
                continue;
            }else if(j>high){
                tmp[start++] = intList[i++];
                continue;
            }
            if (less(intList[i],intList[j])){
                tmp[start++] = intList[i++];
            }else{
                tmp[start++] = intList[j++];
            }
        }
        //把临时数组的内容覆盖到原数组
        for(int q=low;q<=high;q++){
            intList[q] = tmp[q];
        }

    }

    public static Boolean less(Comparable a, Comparable b){

        return a.compareTo(b) < 0;

    }
}