Write insertion sort algorithm. Also discuss its time complexity.

Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages such as simple implementation, efficient for small data sets, more efficient in practice than most other simple quadratic algorithms (i.e., bubble sort, selection sort), and it is stable, adaptive, and in-place.

Here is the step-by-step approach to the insertion sort algorithm:

1. Start from the second element: Consider the first element to be a sorted sub-list of one element. Begin with the second element of the list.

2. Compare with the elements in the sorted sub-list: Compare this second element with the first element. If the second element is greater than the first, leave the element in its place. If it is smaller, swap it with the first element.

3. Iterate through the list: Move to the next element and ensure that it is in the correct place in the sorted sub-list. This means comparing it with all of the previous elements in the sub-list. Shift all the larger elements in the sub-list to make space for the unsorted element.

4. Repeat until the list is sorted: Continue this process of moving through the list, growing the sorted sub-list behind the current position, and inserting the current element into the sorted sub-list at the correct position.

5. End when you reach the end of the list: The list is sorted when you have moved through all the elements.

Here is the pseudocode for the insertion sort algorithm:

function insertionSort(array A)
    for i from 1 to length(A) - 1 do
        value = A[i]
        j = i - 1
        while j >= 0 and A[j] > value do
            A[j + 1] = A[j]
            j = j - 1
        end while
        A[j + 1] = value
    end for
end function

Time Complexity

The time complexity of the insertion sort algorithm in different scenarios can be tabulated as follows:

Case	Time Complexity	Explanation
Best Case	O(n)	The array is already sorted, and no elements need to be moved.
Average Case	O(n^2)	The array is in random order, and each insertion operation can take up to 'i' comparisons.
Worst Case	O(n^2)	The array is sorted in reverse order, and every insertion operation will take 'i' comparisons.
Space Complexity	O(1)	No additional space is used except for temporary variables, so it's constant space complexity.

Example

Let's sort the array [5, 2, 9, 1, 5, 6] using insertion sort:

1. Start with the second element (2). It is smaller than the first (5), so swap them: [2, 5, 9, 1, 5, 6].
2. Move to the third element (9). It is already in the correct position as it is greater than 5: [2, 5, 9, 1, 5, 6].
3. Move to the fourth element (1). It is smaller than all the previous elements, so it moves to the front: [1, 2, 5, 9, 5, 6].
4. Move to the fifth element (5). It is smaller than 9 but greater than 2, so it is placed between 2 and 5: [1, 2, 5, 5, 9, 6].
5. Move to the sixth element (6). It is smaller than 9 but greater than 5, so it is placed between 5 and 9: [1, 2, 5, 5, 6, 9].

The array is now sorted.