This is a standard implementation of the merge-sort algorithm. It is heavily commented to help you understand it.

Merge-sort is a divide and conquer based algorithm with a very simple premise.  It keeps dividing the provided data set in half until only 1 element remains in each recursive call.  Then it merges the sorted sub-sections of the array on the way back up.

1. Take an array as input.
2. Recursively divide the array in half and merge sort each half (so, one recursive call in each invocation for the left half of the array, and one for the right half).
3. When just one element remains, return that element.
4. After the recursive calls, sort the two halves.  Following the recursive logic, each half will already be sorted in itself.  So, the merge just requires repeatedly taking the next smallest element from either of the halves until both are empty.

 import java.util.Arrays;

 public class MergeSort {

     public static void main(String[] args) {
         int[] arr1 = {1,7,2,9,3,5,2,3,4,7,8,9,6,1,3};
         int[] arr2 = {1,7,2,9,3,5,2,3,4,7,8,9,6,1,3};
         System.out.println("Starting array (unosrted)");
         System.out.println(Arrays.toString(arr1));
         mergeSort(arr1);
         System.out.println("Personal mergesort result:");
         System.out.println(Arrays.toString(arr1));
         Arrays.sort(arr2);
         System.out.println("Built in sort result:");
         System.out.println(Arrays.toString(arr2));

     }

     public static void mergeSort(int[] a) {
         mergeSort(a, new int[a.length], 0, a.length - 1);
     }

     private static void mergeSort(int[] array, int[] buffer,
             int start, int end) {

         //Continue until start is equal to end (i.e. there is only
        //one element left.
         if (start < end) {

             //Calculate the midpoint.
             int mid = (start + end) >>> 1;

             //Recurse and sort the lower and upper halves of the
             //array.
             mergeSort(array, buffer, start, mid);
             mergeSort(array, buffer, mid + 1, end);

             //Merge the resulting arrays together.
             merge(array, buffer, start, mid, end);
         }
     }

     private static void merge(int[] array, int[] buffer, int start,
            int mid, int end) {

         //Copy the full range of elements from the array to the
        //temporary buffer.
         for (int i = start; i <= end; ++i) buffer[i] = array[i];

         int low = start;
         int high = mid + 1;
         int curr = start;

         //While there are still low-half and high-half elements to
        //compare, take the smaller one and add it to the real
        //array from the helper buffer.  Must track lower array
        //index, upper array index, and real array index. Also must
        //remember that this ends when we get to the end of either
        //half of the array.
         while (low <= mid && high <= end) {
             if (buffer[low] <= buffer[high])
                array[curr++] = buffer[low++];
             else 
                array[curr++] = buffer[high++];
         }

         //We got to the end of one of the halves first.  If it was
        //the bottom half, then the upper half is already in the
        //correct position which is fine.  If we got to the end of
        //the upper half first then we need to copy the bottom
        //half's remainder to the end.
         while (low <= mid) {
             array[curr++] = buffer[low++];
         }
     }
 }