class Solution {
    public int[] sortArray(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSort(0, nums.length-1, temp, nums);  
        return temp;   
        
    }
    
    public void mergeSort(int from, int to, int[] temp, int[] origin){
        if (from >= to) {
            return;
        }

        int mid = from + (to-from)/2;
        mergeSort(from, mid, temp, origin);
        mergeSort(mid+1, to, temp, origin);
        merge(from, to, temp, origin);
        
    }
    
    public void merge(int from, int to, int[] temp, int[] origin){
        int mid = from + (to-from)/2;
        int leftStart = from;
        int leftEnd = mid;
        int rightStart = mid+1;
        int rightEnd = to;
        int index = 0;
        while (leftStart<= leftEnd && rightStart <= rightEnd){
          if (origin[leftStart] < origin[rightStart]){
            temp[index++] = origin[leftStart++];
          } else {
            temp[index++] = origin[rightStart++];
        }  
    }
        
        
        while(leftStart<= leftEnd) {
            temp[index++]=origin[leftStart++];
        }
        
        while(rightStart<= rightEnd) {
            temp[index++]=origin[rightStart++];
        }
  }
    
}