Lecture 336:- Analysis of Insertion Sort

Insertion Sort is an elementary comparison-based sorting algorithm with a time complexity that depends on the input data. It is considered efficient for small arrays or partially sorted arrays. Let's analyze the key aspects of Insertion Sort:

Time Complexity:

• Best-case time complexity: O(n)
  • Occurs when the input array is already sorted. In this case, Insertion Sort only requires one comparison per element, and no swaps are needed.
• Average-case time complexity: O(n^2)
  • Occurs when the input array is randomly shuffled or in a random order. In this case, on average, each element needs to be compared with roughly half of the already sorted elements, resulting in approximately n^2/4 comparisons and n^2/4 swaps.
• Worst-case time complexity: O(n^2)
  • Occurs when the input array is sorted in reverse order. In this case, each new element must be compared and swapped with all previous sorted elements until it reaches its correct position, resulting in n(n-1)/2 comparisons and swaps.

Space Complexity:

• Insertion Sort is an in-place sorting algorithm, which means it does not require additional memory proportional to the input size. It uses a constant amount of extra space for temporary variables and loop variables.

Stability:

• Insertion Sort is stable. It preserves the relative order of equal elements in the input array.

Adaptivity:

• Insertion Sort is an adaptive algorithm. If the input array is partially sorted or already sorted, the time complexity improves significantly. This is because fewer comparisons and swaps are needed to place the new elements in their correct positions.

Use Cases:

• Insertion Sort is suitable for small arrays or when the input data is almost sorted or partially sorted.
• It is used as an auxiliary sorting algorithm in hybrid sorting algorithms like Timsort.

Overall, Insertion Sort is simple to implement and is efficient for small data sets or when the data is already partially sorted. However, its time complexity grows rapidly with larger input sizes, making it less efficient for large unsorted arrays compared to more advanced sorting algorithms like Merge Sort or Quick Sort.