mergeSort

 1 package POJ;
 2 
 3 public class Main {
 4 
 5     /**
 6      * 
 7      * MergeSort
 8      * 
 9      */
10     public static void main(String[] args) {
11         Main so = new Main();
12         int[] list = { 6, 4, 2, 3, 1, 5, 10, 4, 9, 8, 11, 7 };
13         int[] result = so.mergeSort(list);
14         for (int a : result)
15             System.out.println(a);
16     }
17 
18     public int[] mergeSort(int[] list) {
19         int[] helper = new int[list.length];
20         mergeSort(list, helper, 0, list.length - 1);
21         return list;
22     }
23 
24     private void mergeSort(int[] list, int[] helper, int low, int high) {
25         // TODO Auto-generated method stub
26         if (low < high) {
27             int mid = (high + low) / 2;
28             mergeSort(list, helper, low, mid);
29             mergeSort(list, helper, mid + 1, high);
30             merge(list, helper, low, mid, high);
31         }
32     }
33 
34     private void merge(int[] list, int[] helper, int low, int mid, int high) {
35         // TODO Auto-generated method stub
36         for (int i = low; i <= high; i++) {
37             helper[i] = list[i];
38         }
39         int helperLeft = low;
40         int helperRight = mid + 1;
41         int current = low;
42         while (helperLeft <= mid && helperRight <= high) {
43             if (helper[helperLeft] <= helper[helperRight]) {
44                 list[current] = helper[helperLeft];
45                 helperLeft++;
46             } else {
47                 list[current] = helper[helperRight];
48                 helperRight++;
49             }
50             current++;
51         }
52         int remaining = mid - helperLeft;
53         for (int i = 0; i <= remaining; i++) {
54             list[current + i] = helper[helperLeft + i];
55         }
56     }
57 }