### Data Structure and Algorithm

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

## Table Of Content

###### 1. Problem to Solve

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

Requirements:

• You are required to use Insertion Sort algorithm when sorting the numbers.
• You are required to implement the algorithm in PHP language.
###### 2. 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:

###### 3. 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.

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).