Write the algorithm of insertion sort and find 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 is stable.

Here is the step-by-step algorithm for insertion sort:

1. Start from the second element: Consider the first element to be already sorted. Begin with the second element of the array.

2. Compare with previous elements: Compare the current element with the previous elements. If the current element is smaller than the previous element, proceed to the next step. If not, the current element is in the correct position, and you can move to the next element in the array.

3. Shift elements: If the current element is smaller than the previous element, shift the larger elements one position up to make space for the swapped element.

4. Insert the current element: Insert the current element into the correct position.

5. Repeat: Repeat steps 2-4 until the entire array is sorted.

Here is the pseudocode for insertion sort:

for i from 1 to length(A) - 1
    key = A[i]
    // Insert A[i] into the sorted sequence A[0..i-1]
    j = i - 1
    while j >= 0 and A[j] > key
        A[j + 1] = A[j]
        j = j - 1
    A[j + 1] = key

Time Complexity of Insertion Sort

The time complexity of insertion sort depends on the input data. It can be described in terms of the number of comparisons and the number of swaps performed.

Here is a table that summarizes the time complexity in different scenarios:

Case	Comparisons	Swaps	Time Complexity
Best Case	The array is already sorted	No swaps needed	O(n)
Average Case	The array is in random order	Approximately n^2/4 comparisons and swaps	O(n^2)
Worst Case	The array is sorted in reverse order	Approximately n^2/2 comparisons and swaps	O(n^2)

The best-case scenario occurs when the array is already sorted. In this case, the algorithm only makes one comparison per element, resulting in a linear time complexity of O(n).

The average and worst-case scenarios occur when the array is in random order or sorted in reverse order, respectively. In these cases, the algorithm may need to compare and swap each element with all the other elements that came before it, resulting in a quadratic time complexity of O(n^2).

Example

Let's consider an example to illustrate how insertion sort works:

Suppose we have the following array: [3, 1, 4, 1, 5, 9, 2, 6]

Here's how insertion sort would sort the array:

Initial array: [3, 1, 4, 1, 5, 9, 2, 6]

Pass 1: [1, 3, 4, 1, 5, 9, 2, 6] // 3 and 1 are swapped
Pass 2: [1, 3, 4, 1, 5, 9, 2, 6] // 4 is already in the correct place
Pass 3: [1, 1, 3, 4, 5, 9, 2, 6] // 1 is moved to the correct position
Pass 4: [1, 1, 3, 4, 5, 9, 2, 6] // 5 is already in the correct place
Pass 5: [1, 1, 3, 4, 5, 9, 2, 6] // 9 is already in the correct place
Pass 6: [1, 1, 2, 3, 4, 5, 9, 6] // 2 is moved to the correct position
Pass 7: [1, 1, 2, 3, 4, 5, 6, 9] // 6 is moved to the correct position

Sorted array: [1, 1, 2, 3, 4, 5, 6, 9]

Each pass involves moving the current element to its correct position in the already sorted part of the array (to the left of the current element). This continues until the entire array is sorted.