## PHP Insertion Sort Algorithm

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)
}
```
0.00 avg. rating (0% score) - 0 votes