Insertion Sort

Insertion sort is a sorting algorithm that builds the final sorted array one item at a time. It works the way we sort playing cards in our hands. It is much less efficient on large lists than more advanced algorithms such as Quick sort, Heap sort, or Merge sort.



									function InsertionSort(&$data, $count) {
	for ($i = 1; $i < $count; $i++)
	{
		$j = $i;

		while ($j > 0)
		{
			if ($data[$j - 1] > $data[$j])
			{
				$data[$j - 1] ^= $data[$j];
				$data[$j] ^= $data[$j - 1];
				$data[$j - 1] ^= $data[$j];

				$j--;
			}
			else
			{
				break;
			}
		}
	}
}
								


Example

									$data = array(-1, 25, -58964, 8547, -119, 0, 78596);
InsertionSort($data, 7);
								


Output

									-58964
-119
-1
0
25
8547
78596