MergeSort.java

import java.util.Arrays;

class MergeSort{
  public static void main(String[] args) {
    Integer[] data =  {305, 65, 7, 90, 120, 110, 8};
    mergeSort(data);
    System.out.println(Arrays.toString(data));
  }

  public static <T extends Comparable<T>>
  void mergeSort(T[] data) {
    mergeSort(data, 0, data.length-1);
  }

  private static <T extends Comparable<T>>
  void mergeSort(T[] data, int min, int max) {
    if (min < max){
      int mid = (min+max)/2;
      mergeSort(data, min, mid);
      mergeSort(data, mid+1, max);
      merge(data, min, mid, max);
    }
  }
  
  private static <T extends Comparable<T>>
  void merge(T[] data, int first, int mid, int last){
    T[] temp = (T[]) (new Comparable[data.length]);
    
    int first1 = first, last1 = mid;
    int first2 = mid+1, last2 = last;
    int index = first1;

    while(first1 <= last1 && first2 <= last2){
      if(data[first1].compareTo(data[first2]) < 0){
        temp[index] = data[first1];
        first1++;
      }else{
        temp[index] = data[first2];
        first2++;
      }
      index++;
    }

    while(first1 <= last1){
      temp[index] = data[first1];
      first1++;
      index++;
    }

    while(first2 <= last2){
      temp[index] = data[first2];
      first2++;
      index++;
    }

    for(index = first; index <= last; index++){
      data[index] = temp[index];
    }
  }
}