Insertion Sort in Data Structure — Algorithm, Working and Advantages

Insertion Sort builds a sorted array incrementally. It takes elements from the unsorted part one at a time and inserts each into its correct position within the already sorted part of the array.

Working

• Start with the second element, treating the first element as a sorted sublist of size 1.
• Compare the current element with elements in the sorted sublist, shifting larger elements one position to the right.
• Insert the current element into its correct position.
• Repeat until the entire array is processed.

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

Complexity

Advantages

• Simple to implement and understand.
• Efficient for small datasets and nearly sorted data.
• Stable — preserves the relative order of equal elements.
• In-place — requires only O(1) additional memory.
• Works well as an online algorithm, since it can sort data as it arrives.