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 stub26         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 stub36         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 }