import java.util.*;

public class MergeSort
{

    private static void merge(int array[], int tempArray[],
                              int leftStart, int rightStart, int rightEnd)
    {
        int leftEnd = rightStart - 1;
        int temp = 0;
        int left = leftStart;
        int right = rightStart;

        // Start merging until one of the halves is exhausted
        while (left <= leftEnd && right <= rightEnd)
        {
            if (array[left] <= array[right])
            {
                tempArray[temp] = array[left];
                left++;
            }
            else
            {
                tempArray[temp] = array[right];
                right++;
            }
            temp++;
        }
    
        // Copy rest of first half
        while (left  <= leftEnd)
        {
            tempArray[temp] = array[left];
            temp++;
            left++;
        }

        // Copy rest of second half
        while (right <= rightEnd)
        {
            tempArray[temp] = array[right];
            temp++;
            right++;
        }
    
        // Copy temp array over original array
        for (int i=0; i < rightEnd - leftStart + 1; i++)
            array[leftStart+i] = tempArray[i];
    }

    private static void mergeSort(int[] array, int[] tempArray,
                  int left, int right)
    {
        if (left < right)
        {
            int center = (left + right) / 2;
            mergeSort(array, tempArray, left, center);
            mergeSort(array, tempArray, center+1, right);
            merge(array, tempArray, left, center+1, right);
        }
    }

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

    public static void main(String[] args)
    {
        Random rand = new Random(90125);
        int size = 500000;
        int[] array = new int[size];
        for (int i=0; i < array.length; i++)
            array[i] = rand.nextInt(size*5);
        System.out.println("starting.");
        mergeSort(array);
        for (int i=0; i < 100; i++)
            System.out.print(array[i] + " ");
        System.out.println();
    }
}