Insertion Sort In PHP

Posted by blainegarrett

May 30, 2008


function insertion_sort4 ($a) {
    for ($i = 1; $i < count($a); ++$i) {
        /* Assume items before a[i] are sorted. */
        /* Pick an number */
        $key = $a[$i];
        /* Do binary search to find out the point where b is inserted. */
        $low = 0; //left
        $high = $i; //right
        $k = 0;

	    while ($low - $high < 0) {
	        $j = floor (($high + $low) / 2);
	        if ($key >= $a[$j]) {
	            $low = $j + 1;
            }
	        else {
	            $high = $j;
            }
        }

	/* Shift items between high and i by 1 */
	    for ($k = $i; $k > $low; $k–) {
	        $a[$k] = $a[$k - 1];
        }
    	$a[$low] = $key;
	}
    return $a;
}