Merge Sort

Merge sort divides an array into halves, recursively sorts them, and merges the two sorted ranges. Its predictable running time and stability make it a fundamental comparison sort.

static void mergeSort(int[] values) {
    int[] buffer = new int[values.length];
    mergeSort(values, buffer, 0, values.length);
}

private static void mergeSort(int[] values, int[] buffer, int low, int high) {
    if (high - low < 2) return;
    int middle = low + (high - low) / 2;
    mergeSort(values, buffer, low, middle);
    mergeSort(values, buffer, middle, high);
    merge(values, buffer, low, middle, high);
}

private static void merge(
        int[] values, int[] buffer, int low, int middle, int high) {
    System.arraycopy(values, low, buffer, low, high - low);
    int left = low;
    int right = middle;
    for (int destination = low; destination < high; destination++) {
        if (left >= middle) values[destination] = buffer[right++];
        else if (right >= high) values[destination] = buffer[left++];
        else if (buffer[left] <= buffer[right]) values[destination] = buffer[left++];
        else values[destination] = buffer[right++];
    }
}

Correctness

Induct on range length. Ranges of length zero or one are sorted. Assuming both recursive calls sort their smaller halves, the merge loop maintains that the output prefix contains the smallest consumed elements in order. At termination, the entire range is sorted and contains exactly the original elements.

Complexity

The recurrence T(n) = 2T(n/2) + Θ(n) gives Θ(n log n) time in every case. The shared buffer uses Θ(n) auxiliary space and recursion uses Θ(log n) stack frames. Peak auxiliary space is Θ(n), not Θ(n log n). This implementation is stable because ties are taken from the left half first, but it is not in-place.