Sorting

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 PHP DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.php 
<?php
function merge_sort($values) {
	if (count($values) <= 1) return $values;
	$mid = intdiv(count($values), 2);
	$left = merge_sort(array_slice($values, 0, $mid));
	$right = merge_sort(array_slice($values, $mid));
	$merged = [];
	$i = 0; $j = 0;
	while ($i < count($left) && $j < count($right)) {
		if ($left[$i] <= $right[$j]) $merged[] = $left[$i++];
		else $merged[] = $right[$j++];
	}
	return array_merge($merged, array_slice($left, $i), array_slice($right, $j));
}

$arr = [5, 1, 4, 2, 8];
echo "[" . implode(", ", merge_sort($arr)) . "]
";

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.