class MergeSort
{   public static void main()
    {   MergeSort obj=new MergeSort();
        int a[]={38, 27, 43, 3, 9, 82, 10};
        for(int i=0; i<a.length; i++) System.out.print(a[i]+" "); System.out.println();
        obj.mergeSort(a);
        for(int i=0; i<a.length; i++) System.out.print(a[i]+" "); System.out.println();
    }//main

    void mergeSort(int array[])
    {   if(array.length > 1)
        {   int elementsInA1 = array.length/2;
            int elementsInA2 = array.length-elementsInA1;
            int arr1[] = new int[elementsInA1];
            int arr2[] = new int[elementsInA2];
            for(int i = 0; i < elementsInA1; i++) arr1[i] = array[i];
            for(int i = 0; i < elementsInA2; i++) arr2[i] = array[elementsInA1+i];
            mergeSort(arr1);
            mergeSort(arr2);
            int i = 0, j = 0, k = 0;
            while(arr1.length != j && arr2.length != k)
            {   if(arr1[j] < arr2[k]) array[i++] = arr1[j++];
                else array[i++] = arr2[k++];
            }
            while(arr1.length != j) array[i++] = arr1[j++];
            while(arr2.length != k) array[i++] = arr2[k++];
        }//if
        //return array;
    }//mergeSort()
}//class