1 /*通过递归实现归并排序 2  * 具有思路：将要排序的数组不断划分，直到只有一个元素的时候停止； 3  * 这是递归的基准条件，返回进行排序。 4  * 归并排序的时间复杂度：O(NlogN):考虑的是复制数据到workarr和workarr到arr的次数 5  *  6  * */ 7 public class MergeWithRecursion { 8     static int items = 6; 9     static int[] arr = {10,8,9,59,2,4};10     public static void main(String[] args) {11         display();12         mergeSort();13         display();14 15     }16     17     public static void mergeSort(){18         int[] workarr = new int[items];19         recMergeSort(workarr,0,items-1);20     }21 22     private static void recMergeSort(int[] workarr, int low, int high) {23         if(low == high){24             return;25         }26         else{27             int mid = (low + high) / 2;28             recMergeSort(workarr,low,mid);29             recMergeSort(workarr,mid+1,high);30             merge(workarr,low,mid+1,high);31         }32         33     }34 35     private static void merge(int[] workarr, int low, int mid, int high) {36         //workarr index37         int j = 0;38         int lowbound = low;39         int midindex = mid - 1;40         int n = high - lowbound + 1;41         //进行归并到工作区数组42         while(low <= midindex && mid <= high){43             if(arr[low] < arr[mid]){44                 workarr[j++] = arr[low++];45             }46             else{47                 workarr[j++] = arr[mid++];48             }49         }50         51         while(low <= midindex){52             workarr[j++] = arr[low++];53         }54         55         while(mid <= high){56             workarr[j++] = arr[mid++];57         }58         59         //将工作区部分有序的数组复制到原来的数组60         for(int i = 0; i < n;i++){61             arr[lowbound + i] = workarr[i];62         }63     }64     65     public static void display(){66         for(int i = 0; i < arr.length;i++){67             System.out.print(arr[i] + " ");68         }69         System.out.println();70     }71 72 }