import java.util.Arrays;

public class MergeSort {
  public static Integer[] sort(Integer[] nums) {
    return splitAndMerge(0, nums.length - 1, nums);
  }

  public static Integer[] splitAndMerge(int start, int end, Integer[] arr) {
    // base case
    int a;
    if (end == start) {
      try {
        a = arr[start];
      } catch (Error e) {
      System.out.println("start: " + start + ", arr: " + Arrays.toString(arr));

      }
      Integer[] res = new Integer[] {arr[start]};
      return res;
    }

    int mid = start + (int)((double)end - (double)start) / 2;

    Integer[] left = splitAndMerge(start, mid, arr);
    Integer[] right = splitAndMerge(mid + 1, end, arr);

    return merge(left, right);
  }

  public static Integer[] merge(Integer[] leftList, Integer[] rightList) {
    // copies array, inefficient space usage, could zipper lists for O(1) space
    int currentLeft = 0;
    int currentRight = 0;
    Integer[] result = new Integer[leftList.length + rightList.length];

    // advance L & R until all numbers have been added to new sorted array
    for( int i = 0; i < result.length; i++) {

      if (currentLeft == leftList.length) {
        int right = rightList[currentRight];
        result[i] = right;
        currentRight++;
        continue;
      }
      if (currentRight == rightList.length) {
        int left = leftList[currentLeft];
        result[i] = left;
        currentLeft++;
        continue;
      }

      int left = leftList[currentLeft];
      int right = rightList[currentRight];

      if (left < right || left == right) {
        result[i] = left;
        currentLeft++;
      } else {
        result[i] = right;
        currentRight++;
      }
    }

    return result;
  }
}