← Back to Data Structures and Algorithms in Python

1. Introduction

Insertion Sort is a simple, comparison-based sorting algorithm. It builds the final sorted list one item at a time. The primary idea is to take one element from the input data and insert it at its correct position into the sorted list until the entire list is sorted.

2. Implementation Steps

1. Begin from the second element (index 1).

2. Compare the current element with the previous element.

3. If the current element is smaller than the previous element, compare it with elements before it. Move each of these elements up to make space for the current element.

4. Insert the current element at its correct position.

5. Repeat the process for each element in the array.

3. Implementation 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
    return arr
# Test the insertion_sort function
arr = [12, 11, 13, 5, 6]
sorted_arr = insertion_sort(arr)
print("Sorted array:", sorted_arr)

Output:

Sorted array: [5, 6, 11, 12, 13]

Explanation:

1. We define the insertion_sort function that takes a list arr as its argument.

2. For each element (starting from the second), we store it in the key variable.

3. We then compare the key with the previous elements. If key is smaller, we shift the previous elements up to make space.

4. Once we find the correct position for key, we insert it in its place.

5. This process is repeated until the entire list is sorted.

Insertion Sort is adaptive, meaning it becomes more efficient when dealing with a partially sorted list. However, its worst-case time complexity remains O(n^2).