//MERGESORT CODE

//Konstantin Voevodski
//CS112A1 Spring 2008


public static void mergeSort(int[] a)
//sorts array a using merge sort
{
    int[] tempArray = new int[a.length];
    mergeSort(a,tempArray,0,a.length-1);
}
    
private static void mergeSort(int[] a, int[] tempArray, int left, int right)
//private recursive merge sort routine
{
    if(left < right)
    {
        int center = (left+right)/2;
        mergeSort(a,tempArray,left,center);
        mergeSort(a,tempArray,center+1,right);
        merge(a,tempArray,left,center+1,right);
    }
}
    
private static void merge(int[] a, int[] tempArray, int leftPos, int rightPos, int rightEnd)
//merges the two sorted halves of the array
{
    int tempPos = leftPos;
    int leftEnd = rightPos-1;
    int numElements = rightEnd - leftPos + 1;
    while(leftPos <= leftEnd && rightPos <= rightEnd)
    {
        if(a[leftPos] < a[rightPos])
            tempArray[tempPos++] = a[leftPos++];
        else
            tempArray[tempPos++] = a[rightPos++]
    }
    while(leftPos <= leftEnd)
        tempArray[tempPos++] = a[leftPos++];
    while(rightPos <= rightEnd)
        tempArray[tempPos++] = a[rightPos++];
    for(int i = 0; i < numElements; i++, rightEnd--)
        a[rightEnd] = tempArray[rightEnd];
}