Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.
<?php
function insertion($list)
{
//start from 1, because the first element is sorted list
for ($i = 1; $i < count($list); $i++)
for ($k = 0; $k < $i; $k++)
{
$temp = $list[$k];
if ($list[$i] < $list[$k])
{
$list[$k] = $list[$i];
$list[$i] = $temp;
}
}
return $list;
}
?>