1. package sort;
    3. import java.util.Arrays;
    5. public class MergeSort {
    7.     public static void sort(int[] arr){
    8.         int[] temp = new int[arr.length];
    9.         sort(arr, 0, arr.length-1, temp);
    10.         System.out.println(Arrays.toString(temp));;
    11.     }
    13.     public static void sort(int[] arr, int left, int right, int[] temp){
    14.         if (left < right){
    15.             int mid = (left+right)/2;
    16.             sort(arr, left, mid, temp);
    17.             sort(arr, mid+1, right, temp);
    18.             merge(arr, left, mid, right, temp);
    19.         }
    20.     }
    22.     private static void merge(int[] arr, int left, int mid, int right, int[] temp){
    23.         int i = left;   //左序列指针
    24.         int j = mid+1;  //右序列指针
    25.         int t = 0;      //临时数组指针
    27.         while (i<=mid && j<=right){
    28.             if(arr[i]<=arr[j])
    29.                 temp[t++] = arr[i++];
    30.             else
    31.                 temp[t++] = arr[j++];
    32.         }
    34.         while (i<=mid){     //将左边剩余元素填充进temp中
    35.             temp[t++] = arr[i++];
    36.         }
    37.         while (j<=right){   //将右序列剩余元素填充进temp中
    38.             temp[t++] = arr[j++];
    39.         }
    40.         t = 0;
    41.         //将temp中的元素全部拷贝到原数组中
    42.         while (left <= right){
    43.             arr[left++] = temp[t++];
    44.         }
    45.     }
    47.     public static void main(String[] args) {
    48.         int []arr = {9,8,7,6,5,4,3,2,1};
    49.         sort(arr);
    50.     }
    51. }