Insertion sorts are good when your data is already partially sorted, or if you have a small collection to sort. That’s about the best I can say for them. Here’s two versions in PHP. The first uses two functions:

function insertion_sort($a)

{

for ($i=1; $i < count($a); $i++)
{
inserter(&$a,$i,$a[$i]);
}
}

function inserter($a,$pos,$a_value)

{

$temp = $a[$pos];

$i = $pos;

while($i >= 0 && $a[$i-1] > $a_value)

{

$a[$i] = $a[$i-1];

$i = $i-1;

}

$a[$i] = $temp;

}

The second uses one function:

function insertion_sort($a)

{

for($j=1; $j < count($a); $j++)
{
$temp = $a[$j];
$i = $j;
while(($i >= 0) && ($a[$i-1] > $temp)){

$a[$i] = $a[$i-1];

$i--;

}

$a[$i] = $temp;

}

}

To test them, use the following code:

$haystack = array(1,5,6,3);

insertion_sort(&$haystack);

print_r ($haystack);