Insertion Sort with list

• Builds the final sorted array one item at a time, O(n^2) but efficient for small datasets.

def insertion_sort(arr):
    # Traverse through 1 to len(arr) elements
    # Iterate through each element in the array starting from the second element
    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
        # Place the key in its correct location
        arr[j + 1] = key

# Example
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)

Step 1.

• We define a function insertion_sort that takes an input list arr.

Step 2.

• The outer loop for i in range(1, len(arr)) iterates through each element of the list, starting from the second element (arr[1]).
• Outer Loop: The algorithm iterates over each element in the array starting from the second element (i ranges from 1 to len(arr) - 1).

Step 3.

• Inside the outer loop, key = arr[i] stores the current element to be compared and inserted into the sorted portion of the list.
• Key: For each iteration, it takes the current element (key = arr[i]) and compares it with the elements in the sorted part of the array (to the left of i).

Step 4.

• The inner while loop while j >= 0 and key < arr[j] shifts elements of arr[0..i-1] that are greater than key to one position ahead of their current position (arr[j + 1] = arr[j]).
• Inner Loop: It then moves the elements of the sorted part of the array that are greater than the key one position to the right, creating space for the key.

Step 5.

• After finding the correct position for key, it is placed in its sorted position with arr[j + 1] = key.
• Placement: Once the correct position for the key is found, it is placed in that position.

Walkthrough for the array [12, 11, 13, 5, 6]

First iteration (i = 1):
Key = 11
Compare 11 with 12 (arr[0]), shift 12 to the right
Place 11 at arr[0]
Result: [11, 12, 13, 5, 6]

Second iteration (i = 2):
Key = 13
Compare 13 with 12 (arr[1]), no shift needed
Result: [11, 12, 13, 5, 6]

Third iteration (i = 3):
Key = 5
Compare 5 with 13 (arr[2]), shift 13 to the right
Compare 5 with 12 (arr[1]), shift 12 to the right
Compare 5 with 11 (arr[0]), shift 11 to the right
Place 5 at arr[0]
Result: [5, 11, 12, 13, 6]

Fourth iteration (i = 4):
Key = 6
Compare 6 with 13 (arr[3]), shift 13 to the right
Compare 6 with 12 (arr[2]), shift 12 to the right
Compare 6 with 11 (arr[1]), shift 11 to the right
Place 6 at arr[1]
Result: [5, 6, 11, 12, 13]