import java.util.*;

public class MergeSort {

    public int[] mergeSort(int[] A, int n) {

        int firstIndex = 0;

        int lastIndext = n-1;

        return mergeSort(A, firstIndex,lastIndext);

    }

    public int[] mergeSort(int[] A, int firstIndex, int lastIndex) {

        int mid = firstIndex + (lastIndex - firstIndex)/2;

        if(firstIndex < lastIndex){

            mergeSort(A, firstIndex,mid);

            mergeSort(A, mid+1,lastIndex);

            mergeArray(A,firstIndex,mid,lastIndex);

        }

        return A;

    }

    public void mergeArray(int[] A, int firstIndex, int mid, int lastIndex){

        int[] temp = new int[lastIndex - firstIndex + 1];

        int k = 0;

        int i = firstIndex, m = mid;

        int j = mid + 1, n = lastIndex;

        while(i <= m && j <= n){

            if(A[i] > A[j]) {

                temp[k++] = A[j++];

            }

            else {

                temp[k++] = A[i++]; 

            }

        }

        while(i <= m){

            temp[k++] = A[i++];

        }

        while(j <= n){

            temp[k++] = A[j++];

        }

        for(int t=0; t<temp.length;){

            A[firstIndex++] = temp[t++];

        }

    }

}