# #Data Structure and Algorithm - Insertion Sort

In this tutorial, we will learn a simple sorting algorithm - Insertion Sort.

## #Problem to Solve

Given a list of numbers as shown below, please sort them in ascending order.

``````\$numbers = [21,25,100,98,89,77];
``````

Requirements:

• You are required to use Insertion Sort algorithm when sorting the numbers.
• You are required to implement the algorithm in PHP language.

## #Pseudocode

Insertion Sort works by maintaining a sorted sub-list, extracting the master list's items one by one and inserting them into a the sub-list until all items are moved from master list to the sub-list.

Pseudocode of Insertion Sort algorithm can be written as follows:

``````FOR each element of the master list

Extract the current item

Locate the position to insert by comparing with items from sub-list

Insert the item to the position

END FOR
``````

## #PHP Implementation

We need a FOR loop and a WHILE loop. We are using the FOR loop to iterate the master list and the WHILE loop to locate the position to insert the item.

``````<?php
\$masterList = [21, 25, 100, 98, 89, 77];

\$subList = [];

for (\$i = 0; \$i < count(\$masterList); \$i++) {

\$extractItem = \$masterList[\$i];

\$subList[] = \$extractItem;

// Locate the position to insert by comparing with items from sub-list
\$positionFound = \$i;

while (\$positionFound > 0 && \$extractItem < \$subList[\$positionFound - 1]) {
\$subList[\$positionFound] = \$subList[\$positionFound - 1];
\$positionFound = \$positionFound - 1;
}

// Insert the item to the position
\$subList[\$positionFound] = \$extractItem;

}

print_r(\$subList);

// Output:
/*
Array
(
[0] => 21
[1] => 25
[2] => 77
[3] => 89
[4] => 98
[5] => 100
)
*/
``````

The only piece that needs a bit of explanation is the probably the WHILE loop. Pay attention to the conditions of the loop, besides the constraint of the sub-list's length, we also need to make sure that we do not run the loop when we extract the first element (\$positionFound=0).