Table of Contents

• About Insertion Sort
• Insertion Sort Algorithm
• Function
• Script
• Time Complexity

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

Explanation:

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.

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

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]

Script

Try it on replit:

https://replit.com/@stafura/InsertionSort#main.php

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:

https://en.wikipedia.org/wiki/Insertion_sort