Merge Sort

 
    public class mergeSort{
        private static int[] aux;
        public static void sort(int[] arr) {
            aux = new int[arr.length];
            sort(arr, 0, arr.length - 1);
        }
        private static void sort(int[] arr, int lo, int hi) {
            if(lo >= hi) return;
            int mid = lo + (hi - lo)/2;
            sort(arr, lo, mid);
            sort(arr, mid + 1, hi);
            merge(arr, lo, mid, hi);
        }
        private static void merge(int[] arr, int lo, int mid, int hi) {
            for(int k = lo; k <= hi; k++) {
                aux[k] = arr[k];
            }
            int i = lo;
            int j = mid + 1;
            for(int k = lo; k <= hi; k++) {
                if(i > mid) arr[k] = aux[j];  //left half exausted, take from right half
                else if(j > hi) arr[k] = aux[i]; //right half exausted, take from left half
                else if(arr[i] < arr[j]) arr[k] = aux[i];
                else arr[k] = aux[j];
            }
        }
    }