Write the algorithm of insertion sort and find its time complexity.

Insertion Sort Algorithm:

Insertion sort is a simple, efficient, and widely used sorting algorithm that works by building a sorted array one element at a time. It starts by comparing the first two elements of the array and swapping them if they are out of order. Then, it compares the second element to the third element and swaps them if they are out of order. This process continues until the last element of the array has been compared to the element before it.

Algorithm:

1. Start with an empty sorted array.
2. Take the first unsorted element and insert it into the sorted array at the correct position.
3. Repeat step 2 until all elements are sorted.

Time Complexity:

The time complexity of insertion sort depends on the input array. In the best case scenario, the array is already sorted, and the algorithm takes O(n) time to run. In the worst case scenario, the array is in reverse order, and the algorithm takes O(n^2) time to run.

Mathematically:

• Best-case time complexity: O(n)
• Average-case time complexity: O(n^2)
• Worst-case time complexity: O(n^2)

Pseudocode:

function insertionSort(A, n)
  for i = 2 to n
    j = i
    while j > 1 and A[j] < A[j - 1]
      swap A[j] and A[j - 1]
      j = j - 1
    end while
  end for
end function

Example:

Consider the following unsorted array:

[5, 3, 1, 2, 4]

Step 1:

Compare the first two elements, 5 and 3. Since 5 > 3, swap them.

[3, 5, 1, 2, 4]

Step 2:

Compare the second element, 5, to the first element, 3. Since 5 > 3, do not swap them.

Step 3:

Compare the third element, 1, to the second element, 5. Since 1 < 5, swap them.

[3, 1, 5, 2, 4]

Step 4:

Compare the fourth element, 2, to the third element, 1. Since 2 > 1, swap them.

[3, 1, 2, 5, 4]

Step 5:

Compare the fifth element, 4, to the fourth element, 5. Since 4 < 5, swap them.

[3, 1, 2, 4, 5]

The array is now sorted.

Insertion sort is a simple and efficient sorting algorithm that is well-suited for small arrays. It is also relatively easy to implement, which makes it a popular choice for educational purposes.