/**
 * Mergesort implementation over arrays.
 * @author Daniel Pade
 */
public class MergeSorter {
  /**
   * Sort an array using the `mergesort' algorithm.
   * @param array The array to sort.
   * @return The sorted array
   */
  public Integer[] sort(Integer[] array) {
    return mergesort(array);
  }

  /**
   * Mergesort recursive algorithm
   * @param array The array to sort.
   * @return The sorted array
   */
  private Integer[] mergesort(Integer[] array) {
    /* Part II: For you to complete */
  }

  /**
   * Merge the two arrays.
   * @param left The left array to merge
   * @param right The right array to merge
   * @return The merged array
   */
  public Integer[] merge(Integer[] left, Integer[] right) {
    int leftI = 0;
    int rightI = 0;
    int newI = 0;
    Integer[] newArr = new Integer[left.length + right.length];

    while (leftI < left.length && rightI < right.length) {
      if (left[leftI] < right[rightI]) {
        newArr[newI] = left[leftI];
        leftI++;
      } else {
        newArr[newI] = right[rightI];
        rightI++;
      }
      newI++;
    }

    // Either the left or the right may still have elements
    for (int i = leftI; i < left.length; i++) { // left
      newArr[newI] = left[i];
      newI++;
    }
    for (int i = rightI; i < right.length; i++) { // right
      newArr[newI] = right[i];
      newI++;
    }
    return newArr;
  }


  /**
   * Prints the elements of the array, delimited by spaces.
   */
  public void printCollection(Integer[] items) {
    for (int i = 0; i < items.length; i++) {
      System.out.print(items[i] + " ");
    }
    System.out.println();
  }
}