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

  • $arr is the pinned PHP array literal [5, 1, 4, 2, 8].
  • The sort mutates $arr in place; no second array is allocated for the sorted result.
  • The outer loop starts at $i = 1 and runs while $i < count($arr), treating the left side as the sorted prefix.
  • $key = $arr[$i] saves the current value before shifting can overwrite its original slot.
  • $j = $i - 1 moves left while $j >= 0 && $arr[$j] > $key.
  • Each shift writes one larger value to the right with $arr[$j + 1] = $arr[$j], then decrements $j.
  • The insertion slot is $arr[$j + 1] = $key after the while loop stops.
  • The trace shows [5, 1, 4, 2, 8] become [1, 5, 4, 2, 8], then [1, 4, 5, 2, 8], then [1, 2, 4, 5, 8].
  • The final echo concatenates [ + implode(", ", $arr) + ], then closes the quoted string after a literal newline, so the output is one bracketed row.
sorted prefix Positions before the scan index are already sorted.
shifting Larger values move one slot right to make room for the key.