Insertion Sort for Nearly Sorted Array

Insertion Sort builds the final sorted array one element at a time, by taking each element and inserting it into its correct position among the already-sorted portion. It is particularly efficient when the input array is nearly sorted — meaning most elements are already close to their final position.

Why It Excels on Nearly Sorted Data

Insertion Sort's inner loop only shifts elements while they are out of order. In a nearly sorted array, very few shifts are needed per element, so the algorithm approaches linear time performance rather than its worst-case quadratic time.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([2, 1, 4, 3, 5, 6, 8, 7]))

Complexity

Practical Uses

• Sorting small arrays, or as the final pass in Hybrid sorts like Timsort.
• Online sorting where elements arrive one at a time and the array stays nearly sorted.
• Efficient for datasets with only a few out-of-place elements, such as slightly updated sorted logs.