Merge sort

/**
 *  Problem 1: Mergesort

 *  Input:     {Array}
 *  Output:    {Array}
 *
 *  Example:   [3,9,1,4,7] --> [1,3,4,7,9]
 */

import java.util.*;

// Worst Time Complexity: O(N * log(N))
// Worst Total (Call Stack + Auxiliary) Space Complexity: O(N)
// Average Time Complexity: O(N * log(N))
// Average Total (Call Stack + Auxiliary) Space Complexity: O(N)
// Stability: Stable
class Mergesort{
  public static int[] compute(int[] input) {
    if (input.length < 2) {
            return input;
    }
    int mid = input.length / 2;
    int[] leftArray = new int[mid];
    int[] rightArray = new int[input.length - mid];
    System.arraycopy(input, 0, leftArray, 0, leftArray.length);
    System.arraycopy(input, mid, rightArray, 0, rightArray.length);
    return merge(compute(leftArray), compute(rightArray));
  }

  private static int[] merge(int[] array1, int[] array2){
    int[] result = new int[array1.length + array2.length];
    for (int i = 0, j = 0; i + j < result.length;) {
        if (j >= array2.length || (i < array1.length && array1[i] < array2[j])) {
            result[i + j] = array1[i];
            i++;
        } else {
            result[i + j] = array2[j];
            j++;
        }
    }
   return result;
   }
}