归并排序

• 将两个的有序数列合并成一个有序数列，我们称之为"归并"。
• 归并排序(Merge Sort)就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。

采用分而治之的思想

import java.util.Arrays;

//归并排序
public class MergeSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr = {1,2,3,2,5,6,9,1,2,3,4,5,8,2,3,6,5,4,1,8,9,7,55,22};
        sortProcess(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

// L,R是起点和终点
    public static void sortProcess(int[] arr,int L,int R) {
        if(arr == null || L >= R) {
            return;
        }
        int mid = L + (R - L)/2; 
        sortProcess(arr,L,mid);
        sortProcess(arr,mid + 1,R);
        merge(arr,L,mid,R);
    }
    
    public static void merge(int[] arr,int L,int mid,int R) {
        int[] help = new int[R - L + 1];
        int idex1 = L, idex2 = mid + 1;
        int i = 0;
        while(idex1 <= mid && idex2 <= R) {
            help[i++] = arr[idex1] <= arr[idex2] ?  arr[idex1++] :arr[idex2++];
        }

//总会有一边先排完，把另一边剩下的装进数组
        while( idex1<=mid) {
            help[i++] = arr[idex1++];
        }
        while(idex2<=R) {
            help[i++] = arr[idex2++];
        }
//将排序后的结果覆盖回原数组     
        for(i = 0;i < help.length;i++) {
            arr[L + i] = help[i];
        }
    }
}