归并排序

算法如图所示

image.png

代码实现

/**
 * @author river
 * @date 2019/1/17 9:18
 **/
public class MergeSortDemon {

    public static void mergeSort(List<Integer> nums){
        mergeSortC(nums,0,nums.size()-1);
    }
    public static void mergeSortC(List<Integer> nums,int start,int end){
        int middle = (start + end ) /2 ;
        // split
        if(start >= end ) {
            return;
        }else{
            mergeSortC(nums,start,middle);
            mergeSortC(nums,middle+1,end);
        }
        // merge and sort
        merge(nums,start,middle,end);

    }
    private static void merge(List<Integer> nums,int start,int midele,int end){

        int i = start;
        int j = midele+1;
        if(start == end)
        {
            return;
        }
        List<Integer> list = Lists.newArrayList();
        int size = end - start + 1;
        for(int times = 0 ; times < size ; times ++){
            if(i> midele){
                list.add(nums.get(j));
                j++;
                continue;
            }
            if((j > end)){
                list.add(nums.get(i));
                i++;
                continue;
            }
            if(nums.get(i) <= nums.get(j) ){
                list.add(nums.get(i));
                i++;
            }else{
                list.add(nums.get(j));
                j++;
            }
        }
        // copy
        for(int times = 0 ; times < size ; times ++){
            list.get(times);
            nums.set(start + times,list.get(times));
        }

    }
    public static void main(String[] args) {
        List<Integer> nums = Lists.newArrayList(1,2,4,6,8,3,5,9,7);
        MergeSortDemon.mergeSort(nums);
        System.out.println(nums);
    }
}

结果

[1, 2, 3, 4, 5, 6, 7, 8, 9]