import java.util.*;
  
public class MergeSort {
    public int[] mergeSort(int[] A, int n) {
        // write code here
        sort(A, 0, n - 1);
        return A;
    }
      
    public void sort(int[] a, int start, int end){
        if(start < end){
            int m = (start + end) / 2;
            sort(a, start, m);
            sort(a, m+1 , end);
            merge(a, start, end, m);
        }
    }
      
    public void merge(int[] a, int start, int end, int m){
        int[] temp = new int[end - start + 1];
        int k = 0;
        int left = start;
        int right =  m + 1;
        while(left<=m && right <=end){
            if(a[left] <= a[right]){
               temp[k ++] = a[left ++];
            }else{
                temp[k++] = a[right ++];
            }
        }
          
        while(left <= m){
            temp[k++] = a[left ++];
        }
          
        while(right <= end){
            temp[k++] = a[right++];
        }
          
        for(int i = 0; i < k; i ++){
            a[i + start] = temp[i];
        }
    }
}