Press the green flag, and then press s.
The time complexity for insertion sort varies depending on the initial order of the input data. Best Case: O(n) (linear time). This occurs when the input array is already sorted. In this scenario, the algorithm only needs to iterate through the list once, performing a single comparison for each element and no swaps. Average Case: O(n²) (quadratic time). For a randomly ordered list, each element must, on average, be compared with about half of the elements in the already sorted portion of the array, resulting in quadratic complexity. Worst Case: O(n²) (quadratic time). This happens when the input array is sorted in reverse order. In this case, every element must be compared and swapped with every element in the sorted sub-array, leading to the maximum number of operations. Key Characteristics: Insertion sort is adaptive, meaning it performs efficiently on data sets that are already substantially sorted. The auxiliary space complexity is O(1), as it is an in-place algorithm that only requires a constant amount of additional memory. While inefficient for large, unsorted datasets, it is one of the fastest algorithms for sorting very small arrays.
