Insertion Sort

Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the final sorted array one element at a time. It works by iterating through the array and for each element, it compares it with the elements before it and inserts it at the correct position in the sorted part of the array.

Here's a step-by-step explanation of the Insertion Sort algorithm:

Insertion Sort has a time complexity of O(n^2), where n is the number of elements in the array. It performs well for small arrays or partially sorted arrays but can be less efficient for large datasets.

Insertion Sort Code in Python

Here's an implementation of the Insertion Sort algorithm in Python:

def insertion_sort(arr):

    n = len(arr)

    # Traverse through the array

    for i in range(1, n):

        key = arr[i]

        j = i - 1

        # Move elements of the sorted part to the right

        # to make space for the current element

        while j >= 0 and arr[j] > key:

            arr[j + 1] = arr[j]

            j -= 1

        # Insert the current element at its correct position

        arr[j + 1] = key

# Example usage:

array = [5, 2, 8, 1, 9, 3]


print("Sorted array:", array)