DEV Community

Cover image for Insertion Sort in PHP
Matus Stafura
Matus Stafura

Posted on

Insertion Sort in PHP

Table of Contents

About Insertion Sort

Insertion sort is a simple sorting that compares each element in the list to the elements that come before it and inserts it into its correct position in the sorted list. This process is repeated until all elements have been inserted into their correct positions and the list is sorted.

In insertion sort, we always start at the second index and compare values to the left (before).

Insertion Sort Algorithm


In insertion sort, we need to check all values, so we use two loops.

  1. Firstly, we start the loop from the index 1.

  2. To track the value of that index, we create a temporary variable temp in case we need to swap it.

  3. To compare to the left, we create a temporary variable j equal to i-1.

  4. Since we do not know how many times we need to loop, we use a while loop.

If the value of temp is less than the value on the left, we swap it and decrement j to check the next value to the left.

Insertion Sort

We also need to stop once there is nothing to check. We add the condition j >= 0 to ensure that we stay within the bounds of the list.

5, we return the sorted array.


function insertionSort(array $a): array
  for ($i = 1; $i < count($a); $i++) {
    $temp = $a[$i];
    $j = $i - 1;
    while ($temp < $a[$j] && $j >= 0) {
      $a[$j + 1] = $a[$j];
      $a[$j] = $temp;
      $j -= 1;
  return $a;

// $list = [5, 2, 8, 9, 1];
// insertionSort($list);
// [1, 2, 5, 8, 9]
Enter fullscreen mode Exit fullscreen mode


Try it on replit:

Time Complexity

The time complexity of the insertion sort algorithm is O(n^2) in the worst-case scenario, where n is the number of elements in the list.

Despite its quadratic time complexity, insertion sort is a simple sorting algorithm that is well-suited to small lists or lists that are nearly sorted.

More Info:

Top comments (0)