Mergesort
›Short versionOpen if you only have a minute.
- Split the range in half, sort both halves, and merge them by taking the smaller front value each time.
- The sort is stable when a tie copies from the left half first. The merge below uses <= for that reason.
- Each merge allocates temporary arrays. Extra memory is linear in n, plus a logarithmic recursion stack.
- Best, average, and worst case are all n log n. The split depends on the length, so a reversed array costs the same shape of work.
- Arrays.sort on objects is Timsort, a stable mergesort that also uses runs already in order. Primitive arrays use a dual-pivot quicksort.
Two sorted halves, then one merge
Recursion stops when a range holds one index. A single element is sorted. On the way back, merge copies the two halves into temporary arrays and writes the smaller head back into arr. The midpoint is l + (r - l) / 2, so the left half is l through m and the right half starts at m + 1.
On [12, 11, 13, 5] the halves become [11, 12] and [5, 13]. The final merge compares the fronts and writes [5, 11, 12, 13].
Stable, with linear extra memory
Mergesort is a . Equal records therefore leave in the order they had in the input. That is the property a later sort by a second field relies on.
The merge spends . Every level of recursion does linear work to merge, and there are log n levels, so best, average, and worst case are all O(n log n). The split follows the length, so a reversed array has the same shape of cost.
The same key sits at the front of both halves. Which copy is written first?
The one from the left half. The merge takes the left value when L[i] <= R[j]. The left half was the earlier slice of the array, so that choice keeps the original order of the tie.
When the library sort takes over
Arrays.sort on an object array, and Collections.sort, already run . Calling the library method gives you that stable bound without maintaining the merge yourself. Primitive Arrays.sort takes a different path: a dual-pivot quicksort, chosen because equal ints have no identity to preserve and the JDK favors speed and a smaller buffer there. Use the code below to see the merge. Use Arrays.sort for the collection.
public class MergeSort {
static void sort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
sort(arr, left, mid);
sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[left + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[mid + 1 + j];
}
int i = 0;
int j = 0;
int k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
sort(arr, 0, arr.length - 1);
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}