Array is sorted!
Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time. It works by dividing the list into a sorted and an unsorted portion, and it repeatedly takes the first element from the unsorted portion and inserts it into the correct position in the sorted portion.
Time Complexity:
Best Case: O(n) (when the array is already sorted)
Average Case: O(n²) (due to nested loops for comparisons and shifts)
Worst Case: O(n²) (when the array is sorted in reverse order)
Space Complexity:
O(1) (in-place sorting; requires a constant amount of additional memory)
Insertion Sort is efficient for small datasets or nearly sorted data but becomes inefficient for larger lists compared to more advanced algorithms.