Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It iterates through the input list, removing one element at a time and then finding the place where it belongs in the sorted list and inserting it there. It repeats this process until the whole list is sorted.

When to use insertion sort

? Insertion sort is efficient for small datasets or nearly sorted lists.

? It is an in-place sorting algorithm, meaning it doesn't require extra space, making it suitable for memory-constrained environments.

When not to use insertion sort

? Insertion sort has an average and worst-case time complexity of O(n^2), making it inefficient for large datasets. For large datasets, other more efficient sorting algorithms like quicksort, mergesort, or heapsort should be used.

? It is not suitable for datasets with a large number of elements or when a faster sorting algorithm is required.

A simple insertion sort example in Python,

def insertion_sort(arr):
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        key = arr[i]
        # Move elements of arr[0..i-1] that are greater than key
        # to one position ahead of their current position
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# Example usage:
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("Sorted array is:", arr)        

I hope you enjoyed this post. Thank you.