Wiki
Insertion sort is another common sorting algorithm. To explain how it works, try to imagine this. There’s a couple of cards on the table and you want to sort them in a correct order. You will pick a card from the table (based on any criteria, it doesn’t really matter, you can just pick the cards up randomly) and put it in your left hand at a correct position. To determine the correct position, you will compare it with every other card in your left hand starting from the right. This is a similar algorithm you might unconsciously use when playing cards with your friends.
Example
<?php
$table = array(7, 3, 9, 6, 5, 1, 2, 0, 8, 4);
$leftHand = insertionSort($table);
var_dump($leftHand);
function insertionSort(array $table) {
$leftHand = array();
foreach ($table as $card) {
if (0 === count($leftHand)) {
$leftHand[] = $card;
} else {
$insertedCard = false;
$reindexedLeftHand = array();
for ($i = count($leftHand)-1; $i >= 0; --$i) {
if ($card >= $leftHand[$i]) {
for ($j = 0; $j <= $i; ++$j) {
$reindexedLeftHand[$j] = $leftHand[$j];
}
$reindexedLeftHand[] = $card;
for ($j = $i+1; $j < count($leftHand); ++$j) {
$reindexedLeftHand[$j+1] = $leftHand[$j];
}
$insertedCard = true;
break;
}
}
if (false === $insertedCard) {
$reindexedLeftHand[] = $card;
foreach ($leftHand as $cardInLeftHand) {
$reindexedLeftHand[] = $cardInLeftHand;
}
}
$leftHand = $reindexedLeftHand;
}
}
return $leftHand;
}
Will result in
array(10) {
[0]=>
int(0)
[1]=>
int(1)
[2]=>
int(2)
[3]=>
int(3)
[4]=>
int(4)
[5]=>
int(5)
[6]=>
int(6)
[7]=>
int(7)
[8]=>
int(8)
[9]=>
int(9)
}