Insertion Sort in Python

Insertion Sort is a simple and intuitive sorting algorithm. The basic idea is to build a sorted sequence, and for each unsorted element, find its proper position in the already sorted part of the sequence by scanning it from back to front. Once the appropriate position is found, the element is inserted.

Example

Below is an implementation of the insertion sort algorithm in Python.

def insertionSort(arr): 
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)): 
        key = arr[i] 
        j = i-1

        # Move elements of arr[0..i-1], that are greater than key,
        # to one position ahead of their current position
        while j >= 0 and key < arr[j]: 
            arr[j+1] = arr[j] 
            j -= 1
        arr[j+1] = key 

# Example array
arr = [12, 11, 13, 5, 6] 
insertionSort(arr) 

# Print the sorted array
print("Sorted array:") 
for i in range(len(arr)): 
    print("%d" % arr[i])

Output:

Sorted array:
5
6
11
12
13

In this example, the insertion sort algorithm takes the unsorted array [12, 11, 13, 5, 6] and sorts it in ascending order by repeatedly inserting each element into its proper position within the sorted portion of the array.