Merge Sort (Top-Down)

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

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this C# DSA implementation can be compared directly with the other languages.

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;
	}
}

Complexity

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

Implementation notes

Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

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.