Merge Sort (Top-Down)

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

Algorithm

Basic Implementation

basic.cs

using System;

class Program {
	static void Main() {
		int[] arr = new int[] { 5, 1, 4, 2, 8 };
		PrintArray(MergeSort(arr));
	}

	static void PrintArray(int[] arr) {
		Console.Write("[");
		for (int i = 0; i < arr.Length; i++) {
			if (i > 0) Console.Write(", ");
			Console.Write(arr[i]);
		}
		Console.WriteLine("]");
	}
	static int[] MergeSort(int[] values) {
		if (values.Length <= 1) return values;
		int mid = values.Length / 2;
		int[] left = values[..mid];
		int[] right = values[mid..];
		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

Keep the explicit algorithmic steps instead of calling a standard-library Array.Sort. The replay is meant to expose comparisons, copy movement, and recursive split/merge state.
Range expressions values[..mid] and values[mid..] allocate managed reference int[] temporaries, and merged is another GC-owned array for the merge result. The i, j, and k loops keep every bounds-checked read/write visible while recursion uses the normal C# call stack.

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.