PHP Program for Insertion Sort Algorithm

Use the insertionSort function in PHP to sort an array by repeatedly inserting elements into their correct position; for example, function insertionSort(array &$arr) { for ($i = 1; $i < count($arr); $i++) { $key = $arr[$i]; $j = $i - 1; while ($j >= 0 && $arr[$j] > $key) { $arr[$j + 1] = $arr[$j]; $j--; } $arr[$j + 1] = $key; } } sorts the array in place.

Examples

Input[5, 2, 9, 1]

Output[1, 2, 5, 9]

Input[3, 3, 2, 1]

Output[1, 2, 3, 3]

Input[]

Output[]

How to Think About It

To sort an array using insertion sort, think of sorting playing cards in your hand. Start from the second element, compare it with elements before it, and insert it into the correct position by shifting larger elements one step right. Repeat this for each element until the whole array is sorted.

Algorithm

1

Start from the second element of the array.

2

Compare the current element with the elements before it.

3

Shift all elements larger than the current element one position to the right.

4

Insert the current element into the correct position.

5

Repeat for all elements until the array is sorted.

Code

php

<?php
function insertionSort(array &$arr) {
    $n = count($arr);
    for ($i = 1; $i < $n; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
}

$numbers = [5, 2, 9, 1];
insertionSort($numbers);
print_r($numbers);

Dry Run

Let's trace the array [5, 2, 9, 1] through the insertion sort code.

1

Start with second element (2)

Compare 2 with 5; since 5 > 2, shift 5 right and insert 2 at position 0. Array becomes [2, 5, 9, 1].

2

Move to third element (9)

9 is greater than 5, no shifting needed. Array stays [2, 5, 9, 1].

3

Move to fourth element (1)

Compare 1 with 9, 5, 2; shift all right and insert 1 at position 0. Array becomes [1, 2, 5, 9].

Iteration	Array State
i=1	[2, 5, 9, 1]
i=2	[2, 5, 9, 1]
i=3	[1, 2, 5, 9]

Why This Works

Step 1: Choosing the key element

The code picks the element at index i as the key to insert into the sorted part on the left.

Step 2: Shifting elements

Elements larger than the key are moved one position right to make space for the key.

Step 3: Inserting the key

The key is placed in the correct position where all elements before it are smaller or equal.

Alternative Approaches

Using built-in sort

php

<?php
$arr = [5, 2, 9, 1];
sort($arr);
print_r($arr);

This is simpler and faster for real use but does not teach the insertion sort algorithm.

Recursive insertion sort

php

<?php
function recursiveInsertionSort(array &$arr, int $n) {
    if ($n <= 1) return;
    recursiveInsertionSort($arr, $n - 1);
    $last = $arr[$n - 1];
    $j = $n - 2;
    while ($j >= 0 && $arr[$j] > $last) {
        $arr[$j + 1] = $arr[$j];
        $j--;
    }
    $arr[$j + 1] = $last;
}

$arr = [5, 2, 9, 1];
recursiveInsertionSort($arr, count($arr));
print_r($arr);

Uses recursion instead of loops, which is less efficient but shows a different approach.

Complexity: O(n^2) time, O(1) space

Time Complexity

Insertion sort uses nested loops: the outer loop runs n times, and the inner loop can run up to n times in the worst case, resulting in O(n^2) time.

Space Complexity

It sorts the array in place without extra arrays, so space complexity is O(1).

Which Approach is Fastest?

Built-in PHP sort functions are faster and optimized, but insertion sort is useful for learning and small datasets.

Approach	Time	Space	Best For
Insertion Sort	O(n^2)	O(1)	Small or nearly sorted arrays
Built-in sort()	O(n log n)	O(1)	General use, large arrays
Recursive Insertion Sort	O(n^2)	O(n) due to recursion stack	Learning recursion