public int[] mergeSort(int[] array) {
  if (array.length == 1) return array;

  int start = 0;
  int end = array.length;
  int middle = (end-start)/2;

  int[] left = Arrays.copyOfRange(array, start, middle);
  int[] right = Arrays.copyOfRange(array, middle, end);

  int[] sortedLeft = mergeSort(left);
  int[] sortedRight = mergeSort(right);

  return merge(sortedLeft, sortedRight);
}

private int[] merge(int[] first, int[] second) {
  int[] result = new int[first.length + second.length];

  int posFirst = 0;
  int posSecond = 0;
  int posResult = 0;

  while (posResult < result.length) {
      if (posFirst == first.length) {
          result[posResult++] = second[posSecond++];
      }
      else if (posSecond == second.length) {
          result[posResult++] = first[posFirst++];
      }
      else if (first[posFirst] > second[posSecond]) {
          result[posResult++] = second[posSecond++];
      } else {
          result[posResult++] = first[posFirst++];
      }
  }
  return result;
}