MergeSort

import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    Test test = new Test();
    test.runTests();
  }
}

class Test{
  private MergeSort mergeSort;
  private int[] array;
  
  public void runTests(){
    startTest();
    System.out.println("Before Merge: " + Arrays.toString(array));
    mergeSort.merge(array, 4, 7, 11);
    System.out.println("After Merge: " + Arrays.toString(array));
    
    startTest();
    System.out.println("Before Sort: " + Arrays.toString(array));
    mergeSort.sort(array, 0, array.length - 1);
    System.out.println("After Sort: " + Arrays.toString(array));
  }
  
  private void startTest(){
    mergeSort = new MergeSort();
    array = new int[]{16, 4, 10, 14, 3, 5, 9, 10, 7, 8, 9, 10, 3, 2, 8, 1};
  }
}

class MergeSort{
  public void sort(int[] array, int low, int heigh){
    if(low < heigh){
      int mid = (int) Math.floor((heigh + low) / 2.0);
      sort(array, low, mid);
      sort(array, mid + 1, heigh);
      merge(array, low, mid, heigh);
    }
  }
  
  public void merge(int[] array, int low, int mid, int heigh){
    int[] leftArray = new int[mid - low + 2];
    int[] rightArray = new int[heigh - mid + 1];
    int sentinel = Integer.MAX_VALUE;
    
    // copy
    leftArray[leftArray.length - 1] = sentinel;
    rightArray[rightArray.length - 1] = sentinel;
    System.arraycopy(array, low, leftArray, 0, mid - low + 1);
    System.arraycopy(array, mid + 1, rightArray, 0, heigh - mid);
    
    // merge
    int i = 0, j = 0;
    for(int k = low; k <= heigh; k++){
      if(leftArray[i] <= rightArray[j]){
        array[k] = leftArray[i];
        i++;
      }else{
        array[k] = rightArray[j];
        j++;
      }
    }
  }
}