Time and Space Complexity

Time Complexity:

• Best Case: O(n)
  • When the array is already sorted, Insertion Sort makes only one pass to confirm the sorted order.
• Average and Worst Case: O(n²)
  • In the average and worst cases, it takes quadratic time because, for each element, we may need to compare and shift through the entire sorted portion.

Space Complexity:

• O(1)
  • Insertion Sort is an "in-place" algorithm, meaning it doesn't require additional memory proportional to the input size.
  • The space used for sorting remains constant, regardless of the input size.

Summary:

• Insertion Sort is efficient for small datasets or nearly sorted arrays.
• It's less suitable for large datasets due to its quadratic time complexity.
• The space complexity is constant, making it memory-efficient for any input size.