Pseudocode of Insertion sort with Time Complexity Analysis

Insertion Sort is a simple sorting algorithm that picks an element from the unsorted position and inserts it into its correct position in the array. This algorithm works by comparing the current element with the elements before it. And shifting them to the right until the correct position is found.

Pseudocode of Insertion Sort

InsertionSort(A):
    for i = 1 to length(A) - 1 do
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key do
            A[j + 1] = A[j]
            j = j - 1
        A[j + 1] = key

Explanations

for loop iterates the array A from index 1 to the last element (index length(A) – 1).
Inside the for loop, there is a variable “key” that store the current element. This variable key keeps track of the value being inserted into its correct position.
variable j is set to the index one less than the current element’s index.
While loop compares key with the elements before it, shifting them to the right if they are greater than key.
The loop continues until it reaches the beginning of the array (j = 0) or until it finds an element that is smaller or equal to key.
In the while loop, A[j + 1] = A[j] shifts the elements one position to the right. This shifting creates space for key in its correct position.
when while loop terminates, key is inserted into its correct position by assigning it to A[j + 1]
The outer for loop continues with the next element, repeating the process until all elements are sorted.

Example of Insertion Sort

Imagine we have a list of numbers: A = [5, 3, 4, 1, 2]

Initial List:

A = [5, 3, 4, 1, 2]

Step 1: (i=1, key=A[1]=3)

Compare key (3) with A[0] (5). Since 3 < 5, we move 5 one position to the right.
Insert 3 into its correct position.

Result: A = [3, 5, 4, 1, 2]

Step 2: (i=2, key=A[2]=4)

Compare key (4) with A[1] (5). Since 4 < 5, move 5 one position to the right.
Then, compare key (4) with A[0] (3). Since 4 > 3, insert 4 right after 3.

Result: A = [3, 4, 5, 1, 2]

Step 3: (i=3, key=A[3]=1)

Compare key (1) with A[2] (5), move 5 to the right.
Compare key (1) with A[1] (4), move 4 to the right.
Compare key (1) with A[0] (3), move 3 to the right.
Insert 1 into the first position.

Result: A = [1, 3, 4, 5, 2]

Step 4: (i=4, key=A[4]=2)

Compare key (2) with A[3] (5), move 5 to the right.
Compare key (2) with A[2] (4), move 4 to the right.
Compare key (2) with A[1] (3), move 3 to the right.
Insert 2 after 1.

Final Result: A = [1, 2, 3, 4, 5]

After following these steps, our list is now sorted. The algorithm works by taking each element in turn, finding its correct position in the sorted part of the list, and inserting it there. This continues until all elements are sorted. Insertion Sort is intuitive and works well for small lists or lists that are already nearly sorted.

Time Complexity Analysis

Best-case time complexity: Best case can be considered when the input array is already sorted. It means the algorithm will only perform the comparisons but there will be no element shifting. In this case, the time complexity is Θ(n), where n is the number of elements in the array.
Worst-case time complexity: The worst case will be, suppose the given array is in reverse order. In this condition, each element of the array will be compared and shifted to its correct position. The worst-case time complexity is O(n^2).
Average-case time complexity: On average case, Insertion Sort performs Θ(n^2) comparisons and shifts.

Insertion Sort is an efficient algorithm to sort the small input sizes array. It is also a good option for partially sorted arrays.

Following properties of Insertion sort are:

In-place sorting: Insertion Sort perform sorting of the elements by modifying the elements in-place without taking additional memory.
Stable sorting: The algorithm maintains the relative order of elements with equal values, making it a stable sorting algorithm.
Adaptive sorting: If the input array is already partially sorted, Insertion Sort can take advantage of this and perform fewer comparisons and shifts.

However, Insertion Sort is not suitable for large input sizes. It is because of its quadratic time complexity. It becomes inefficient if we compare it with more advanced sorting algorithms like Quick Sort or Merge Sort. These advanced sorting algorithms have better average-case and worst-case time complexities.

Overall, Insertion Sort is a simple and easy-to-implement sorting algorithm. But It is more suitable for small-size arrays and partially sorted arrays.

Pseudocode of Insertion sort with Time Complexity Analysis