Design an algorithm for performing insertion sort. Analyze its time efficiency

Design an algorithm for performing insertion sort. Analyze its time efficiency; apply the same to sort the following number. 89 45 68 90 29 34 17

Insertion Sort is a simple and intuitive comparison-based sorting algorithm. It builds the sorted array one element at a time by repeatedly taking the next element and inserting it into its correct position within the already sorted part of the array.

Algorithm for Insertion Sort:

1. Start with the second element (index 1) assuming the first element (index 0) is already sorted.
2. Compare the current element with the previous elements, moving larger elements to the right to make space for the current element.
3. Repeat this process for all elements, effectively “inserting” each element into its correct position in the sorted part of the array.
4. Continue until the entire array is sorted.

Apply Insertion Sort to sort the given set of numbers: 89, 45, 68, 90, 29, 34, 17.

1. Step-by-step Sorting:

• Start with assuming the first element is already sorted.

   [89, | 45, 68, 90, 29, 34, 17]

• Insert the next element (45) in its correct position in the sorted part.

   [45, 89, | 68, 90, 29, 34, 17]

• Insert the next element (68) in its correct position in the sorted part.

   [45, 68, 89, | 90, 29, 34, 17]

• Continue this process for the remaining elements.

1. Final Sorted Array:

   [17, 29, 34, 45, 68, 89, 90]

Time Efficiency Analysis:

• Best Case Time Complexity: O(n)
• Average Case Time Complexity: O(n^2)
• Worst Case Time Complexity: O(n^2)

In the best case, when the array is already sorted, each element is compared only with the previous elements until it finds its correct position, resulting in a linear time complexity.

In the average and worst cases, Insertion Sort performs nested loops to compare and move elements, leading to a quadratic time complexity, making it inefficient for large datasets compared to more efficient sorting algorithms like Merge Sort or Quick Sort.

For the given input [89, 45, 68, 90, 29, 34, 17], Insertion Sort takes the following number of comparisons and swaps in the worst case:

• Comparisons: O(n^2)
• Swaps: O(n^2)

However, in the best-case scenario (already sorted input), Insertion Sort only requires O(n) comparisons and swaps.