package POJ;

 public class Main {

     /**

      *

      * MergeSort

      *

      */

     public static void main(String[] args) {

         Main so = new Main();

         int[] list = { 6, 4, 2, 3, 1, 5, 10, 4, 9, 8, 11, 7 };

         int[] result = so.mergeSort(list);

         for (int a : result)

             System.out.println(a);

     }

     public int[] mergeSort(int[] list) {

         int[] helper = new int[list.length];

         mergeSort(list, helper, 0, list.length - 1);

         return list;

     }

     private void mergeSort(int[] list, int[] helper, int low, int high) {

         // TODO Auto-generated method stub

         if (low < high) {

             int mid = (high + low) / 2;

             mergeSort(list, helper, low, mid);

             mergeSort(list, helper, mid + 1, high);

             merge(list, helper, low, mid, high);

         }

     }

     private void merge(int[] list, int[] helper, int low, int mid, int high) {

         // TODO Auto-generated method stub

         for (int i = low; i <= high; i++) {

             helper[i] = list[i];

         }

         int helperLeft = low;

         int helperRight = mid + 1;

         int current = low;

         while (helperLeft <= mid && helperRight <= high) {

             if (helper[helperLeft] <= helper[helperRight]) {

                 list[current] = helper[helperLeft];

                 helperLeft++;

             } else {

                 list[current] = helper[helperRight];

                 helperRight++;

             }

             current++;

         }

         int remaining = mid - helperLeft;

         for (int i = 0; i <= remaining; i++) {

             list[current + i] = helper[helperLeft + i];

         }

     }

 }