Sorting

Merge Sort (Top-Down)

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

Algorithm

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)) . "]
";

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].

Top-down split used by merge_sort.[5,1,4,2,8]mid = 2[5,1]left[4,2,8]right

Step 2 - Sorted halves return

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

Returned subarrays before the final merge.sidebefore sortafter sortleft[5, 1][1, 5]right[4, 2, 8][2, 4, 8]

Step 3 - Merge by taking smaller fronts

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

Final merge produces [1, 2, 4, 5, 8].choiceleft frontright frontmergedtake 112[1]take 252[1, 2]take 454[1, 2, 4]extend58[1, 2, 4, 5, 8]

Complexity

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

Implementation notes

  • $arr is the pinned PHP array literal [5, 1, 4, 2, 8].
  • merge_sort($values) returns a sorted array; it does not mutate $arr in place.
  • The base case is if (count($values) <= 1) return $values;.
  • $mid = intdiv(count($values), 2) splits the array with integer division.
  • array_slice($values, 0, $mid) creates the left half, and array_slice($values, $mid) creates the right half.
  • $merged = [] collects output while $i and $j index the sorted left and right arrays.
  • The merge comparison is $left[$i] <= $right[$j], so equal values would keep the left-side value first.
  • Appends use $merged[] = ..., and leftovers are joined with array_merge($merged, array_slice($left, $i), array_slice($right, $j)).
  • The trace shows top-level halves [5, 1] and [4, 2, 8], sorted as [1, 5] and [2, 4, 8], then merged into [1, 2, 4, 5, 8].
  • The final echo concatenates [ + implode(", ", merge_sort($arr)) + ], then closes the quoted string after a literal newline, so the output is one bracketed row.
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.