MergeSort.java

import java.util.ArrayList;
import java.util.List;

public class MergeSort {
  public static <T extends Comparable<T>> void sort(List<T> list) {
    sort(list, 0, list.size());
  }

  private static <T extends Comparable<T>> void sort(List<T> list, int start, int end) {
    if (end - start < 2) return;
    int mid = start + (end - start) / 2;
    sort(list, start, mid);
    sort(list, mid, end);
    merge(list, start, mid, end);
  }

  private static <T extends Comparable<T>> void merge(List<T> list, int start, int mid, int end) {
    List<T> aux = new ArrayList<>();

    int i = start;
    int j = mid;

    while (i < mid && j < end) {
      if (list.get(i).compareTo(list.get(j)) <= 0) {
        aux.add(list.get(i));
        i++;
      } else {
        aux.add(list.get(j));
        j++;
      }
    }

    while (i < mid) {
      aux.add(list.get(i));
      i++;
    }

    while (j < end) {
      aux.add(list.get(j));
      j++;
    }

    for (int k = 0; k < end - start; k++) {
      list.set(start + k, aux.get(k));
    }
  }

  public static <T extends Comparable<T>> void sort(T[] arr) {
    sort(arr, 0, arr.length);
  }

  private static <T extends Comparable<T>> void sort(T[] arr, int start, int end) {
    if (end - start < 2) return;
    int mid = start + (end - start) / 2;
    sort(arr, start, mid);
    sort(arr, mid, end);
    merge(arr, start, mid, end);
  }

  private static <T extends Comparable<T>> void merge(T[] arr, int start, int mid, int end) {
    List<T> aux = new ArrayList<>();

    int i = start;
    int j = mid;

    while (i < mid && j < end) {
      if (arr[i].compareTo(arr[j]) <= 0) {
        aux.add(arr[i]);
        i++;
      } else {
        aux.add(arr[j]);
        j++;
      }
    }

    while (i < mid) {
      aux.add(arr[i]);
      i++;
    }

    while (j < end) {
      aux.add(arr[j]);
      j++;
    }

    for (int k = 0; k < end - start; k++) {
      arr[start + k] = aux.get(k);
    }
  }
}

MergeSortTest.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import org.junit.Test;

import static org.assertj.core.api.Assertions.assertThat;

public class MergeSortTest {
  @Test
  public void test_with_arrays() {
    List<Integer> nums = IntStream.range(0, 100).boxed().collect(Collectors.toList());
    Collections.shuffle(nums);

    Integer[] arr = nums.toArray(new Integer[0]);
    Integer[] arr2 = arr.clone();

    MergeSort.sort(arr);
    Arrays.sort(arr2);
    assertThat(Arrays.toString(arr)).isEqualTo(Arrays.toString(arr2));
  }

  @Test
  public void test_with_list() {
    List<Integer> nums = IntStream.range(0, 100).boxed().collect(Collectors.toList());
    Collections.shuffle(nums);

    List<Integer> nums2 = new ArrayList<>(nums);

    MergeSort.sort(nums);
    Collections.sort(nums2);
    assertThat(nums2.toString()).isEqualTo(nums.toString());
  }
}