1 package com.sort.demo;
 2 
 3 public class Mergesort extends Sort {
 4 
 5     @Override
 6     public void sort(int[] arr) {
 7         if (arr==null||arr.length<2) return;
 8         processSort(arr,0,arr.length-1);
 9     }
10 
11     public void processSort(int[] arr, int L, int R) {
12         if (L == R)
13             return;
14         int mid = (L + R) / 2;
15         //左邊排序
16         processSort(arr, L, mid);
17         //右邊排序
18         processSort(arr, mid + 1, R);
19         merge(arr,L,mid,R);
20     }
21 
22     public void merge(int[] arr, int L, int mid, int R) {
23 
24         if (arr==null||arr.length<2) return;
25         int[] help=new int[R-L+1];
26         int i=0;
27         int p1=L;
28         int p2=mid+1;
29         //左右兩邊的有序數組都不越界
30         while (p1<=mid&&p2<=R){
31             help[i++]=arr[p1]>arr[p2]?arr[p2++]:arr[p1++];
32         }
33         //右邊越界，左邊依次copy到結果數組
34         while (p1<=mid){
35             help[i++]=arr[p1++];
36         }
37 //        左邊越界，右邊依次copy到結果數組
38         while (p2<=R){
39             help[i++]=arr[p2++];
40         }
41         //再copy回原數組
42         for(i=0;i<help.length;i++){
43 //            很容易出錯的地址，這個地方應該是L+i,而不是i，因為從arr的L到R合并
44             arr[L+i]=help[i];
45         }
46     }
47 
48     public static void main(String[] args) {
49         Mergesort sort=new Mergesort();
50         Test.test(sort);
51     }
52 }