import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
    public static void mergeSort(int[] data, int start, int end) {
        if(start < end) {
            int mid = (start + end) / 2;
            mergeSort(data, start, mid);
            mergeSort(data, mid + 1, end);
            merge(data, start, mid, end);
        }
    }
    public static void merge(int[] data, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        System.out.println(start +" "+ mid +" "+end);
        
        // i --> starting of left subarray, j--> starting of right subarray
        // mid --> Ending of left subarray, end--> Ending of right subarray
        // k--> pointer for temp array
        int i = start, j = mid + 1, k = 0;
        
        // Ist merge i.e both left and right subarrays have values 
        while(i <= mid && j <= end) {
            if(data[i] <= data[j]) 
                temp[k++] = data[i++];
            else    
                temp[k++] = data[j++];
        }
        
        // 2nd merge i.e run only when left subrray is remaining to be merged
        // and right subrray is done with merging
        while(i <= mid) {
            temp[k++] = data[i++];
        }
        
        // 2nd merge i.e run only when right subrray is remaining to be merged
        // and left subrray is done with merging
        while(j <= end) {
            temp[k++] = data[j++];
        }
        
        // putting back sorted values from temp into the original array
        for(i = start; i <= end; i++) {
            data[i] = temp[i - start];
        }
        
    }
	public static void main (String[] args) throws java.lang.Exception
	{
	    int data[] = {38, 27, 43, 3, 9, 82, 10};
		mergeSort(data, 0 , data.length - 1);
		for(int num : data) {
		    System.out.print(num +" ");
		}

	}
}