1  public class MergeSort {
  2    /** The method for sorting the numbers */
  3    public static void mergeSort(int[] list) {
  4      if (list.length > 1) {
  5        // Merge sort the first half
  6        int[] firstHalf = new int[list.length / 2];
  7        System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
  8        mergeSort(firstHalf);
  9  
 10        // Merge sort the second half
 11        int secondHalfLength = list.length - list.length / 2;
 12        int[] secondHalf = new int[secondHalfLength];
 13        System.arraycopy(list, list.length / 2,
 14          secondHalf, 0, secondHalfLength);
 15        mergeSort(secondHalf);
 16  
 17        // Merge firstHalf with secondHalf into list
 18        merge(firstHalf, secondHalf, list);
 19      }
 20    }
 21  
 22    /** Merge two sorted lists */
 23    public static void merge(int[] list1, int[] list2, int[] temp) {
 24      int current1 = 0; // Current index in list1
 25      int current2 = 0; // Current index in list2
 26      int current3 = 0; // Current index in temp
 27  
 28      while (current1 < list1.length && current2 < list2.length) {
 29        if (list1[current1] < list2[current2])
 30          temp[current3++] = list1[current1++];
 31        else
 32          temp[current3++] = list2[current2++];
 33      }
 34  
 35      while (current1 < list1.length)
 36        temp[current3++] = list1[current1++];
 37  
 38      while (current2 < list2.length)
 39        temp[current3++] = list2[current2++];
 40    }
 41  
 42    /** A test method */
 43    public static void main(String[] args) {
 44      int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
 45      mergeSort(list);
 46      for (int i = 0; i < list.length; i++)
 47        System.out.print(list[i] + " ");
 48    }
 49  }