Merge Sort

average O(n log n) - best O(n log n) - worst O(n log n)

space O(n)

public static void mergeSort(int[] a, int low, int high){
    while (low < high) {
        int mid = low + (high - low) / 2;
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        merge(a, low, mid, high);
    }
}

public static void merge(int[] a, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int left = low;
    int right = mid + 1;
    int idx = 0;
    while (left <= mid && right <= high) {
        if (a[left] < a[right]) {
            temp[idx++] = a[left++];
        } else {
            temp[idx++] = a[right++];
        }
    }
    while (left <= mid) {
        temp[idx++] = a[left++];
    }
    while (right <= high) {
        temp[idx++] = a[right++];
    }

    //put back to original array
    for (int t = 0; t < temp.length; t++) {
        a[low + t] = temp[t];
    }
}

junchao's version

public static void mergeSort(int[] ints) {
    if (ints == null || ints.length == 0) {
        return;
    }

    int[] aux = new int[ints.length];
    mergeSortHelper(ints, aux, 0, ints.length - 1);
}

/** Merge sorts [ints[lo], ints[hi]]. */
private static void mergeSortHelper(int[] ints, int[] aux, int lo, int hi) {
    if (lo >= hi) {
        return;
    }

    int mid = lo + (hi - lo) / 2;
    mergeSortHelper(ints, aux, lo, mid);
    mergeSortHelper(ints, aux, mid + 1, hi);

    merge(ints, aux, lo, mid, hi);
}

private static void merge(int[] ints, int[] aux, int lo, int mid, int hi) {
    for (int k = lo; k <= hi; k++) {
        aux[k] = ints[k];
    }

    int i = lo; // Left half index
    int j = mid + 1; // Right half index

    for (int k = lo; k <= hi; k++) {
        if (i > mid) {
            ints[k] = aux[j];
            j++;

        } else if (j > hi) {
            ints[k] = aux[i];
            i++;

        } else if (aux[j] < aux[i]) {
            ints[k] = aux[j];
            j++;

        } else {
            ints[k] = aux[i];
            i++;
        }
    }
}