Sorting

Insertion Sort

Build the sorted prefix one item at a time, shifting larger values right until the current key can be inserted.

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
$arr = [5, 1, 4, 2, 8];
for ($i = 1; $i < count($arr); $i++) {
	$key = $arr[$i];
	$j = $i - 1;
	while ($j >= 0 && $arr[$j] > $key) {
		$arr[$j + 1] = $arr[$j];
		$j--;
	}
	$arr[$j + 1] = $key;
}
echo "[" . implode(", ", $arr) . "]
";

Complexity

  • Time: O(n^2) worst and average, O(n) best
  • Space: O(1)
  • 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.
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.