Merge Sort (Top-Down)

Split the array recursively, sort each half, then merge two sorted runs into one sorted result.

Algorithm

Basic Implementation

Basic.java

class Basic {
	public static void main(String[] args) {
		int[] arr = new int[] { 5, 1, 4, 2, 8 };
		int[] sorted = mergeSort(arr);
		printArray(sorted);
	}

	static void printArray(int[] arr) {
		System.out.print("[");
		for (int i = 0; i < arr.length; i++) {
			if (i > 0) System.out.print(", ");
			System.out.print(arr[i]);
		}
		System.out.println("]");
	}
	static int[] mergeSort(int[] values) {
		if (values.length <= 1) return values;
		int mid = values.length / 2;
		int[] left = java.util.Arrays.copyOfRange(values, 0, mid);
		int[] right = java.util.Arrays.copyOfRange(values, mid, values.length);
		return merge(mergeSort(left), mergeSort(right));
	}

	static int[] merge(int[] left, int[] right) {
		int[] merged = new int[left.length + right.length];
		int i = 0, j = 0, k = 0;
		while (i < left.length && j < right.length) {
			if (left[i] <= right[j]) merged[k++] = left[i++];
			else merged[k++] = right[j++];
		}
		while (i < left.length) merged[k++] = left[i++];
		while (j < right.length) merged[k++] = right[j++];
		return merged;
	}
}

The pinned input is [5, 1, 4, 2, 8]. The diagrams show the split into recursive halves, the sorted subarrays, and the final merge choices.

Step 1 - Split the input

The first midpoint splits [5, 1, 4, 2, 8] into left [5, 1] and right [4, 2, 8].

Step 2 - Sorted halves return

Recursive calls return [1, 5] and [2, 4, 8] before the final merge begins.

Step 3 - Merge by taking smaller fronts

Take 1 from left, then 2 and 4 from right, then the remaining 5 and 8.

Complexity

Time: O(n log n)
Space: O(n)
Stable: yes

Implementation notes

Java stores values in primitive int[] arrays. mergeSort returns an int[] result instead of sorting the original array in place, and the base case returns the same one-element or empty array reference.
Each recursive split computes mid = values.length / 2 and allocates copied halves with java.util.Arrays.copyOfRange(values, 0, mid) and copyOfRange(values, mid, values.length).
merge allocates a fresh int[] merged and uses index variables i, j, and k to copy primitive values from the sorted halves. The left[i] <= right[j] comparison preserves left-side ties before the tail-copy loops run.
The replay shows the top-level copied halves [5, 1] and [4, 2, 8], their sorted recursive results, then the final merged array [1, 2, 4, 5, 8]. Split and merge arrays are JVM heap objects while referenced; temporary arrays become reclaimable after returns, while the final merged array remains referenced as sorted.

divide and conquer Each recursive call solves a smaller sorted subproblem.

merge step Two sorted halves are combined by repeatedly taking the smaller front item.