Insertion Sort

Insertion sort is a sorting algorithm that builds the final sorted list one element at a time. Like selection sort, it divides the list into two parts: a sorted section and an unsorted section. The key difference is in how elements are moved. In insertion sort, each element from the unsorted part is taken one by one and inserted into its correct position within the sorted part.

The name comes from the way the algorithm works. In each pass, the sorted list is traversed from the backward direction (right to left) to find the spot where the next unsorted element should be placed. This backward scan is what makes it "insertion" sort — you are inserting a new card into an already sorted hand, checking from the largest card down.

How the passes work

• Pass 1: The sorted list starts with just one element (say element $s$). The unsorted list has $n-1$ elements. The first element of the unsorted list (say element $e$) is compared with $s$. If $e$ is smaller than $s$, then $s$ is shifted one position to the right, making space for $e$ to be inserted. After this pass, the sorted list has 2 elements and the unsorted list has $n-2$ elements.

• Pass 2: The first element of the remaining unsorted list is compared with each element of the sorted list, starting from the backward direction (i.e., from the largest element in the sorted part). As the comparison moves leftwards, any element in the sorted list that is larger than the unsorted element is shifted one position to the right. This shifting creates a gap where the unsorted element can be inserted. Once the correct position is found (where the element to the left is smaller or equal), the unsorted element is placed there.

• Subsequent passes: This process continues. In each pass, one more element from the unsorted part is inserted into its correct place in the sorted part. The sorted part grows by one element each time, and the unsorted part shrinks by one. The algorithm stops when all elements from the unsorted list have been inserted.

Example walkthrough

Consider the list numList = [8, 7, 13, 1, -9, 4]. The figure in the textbook (Figure 5.3) shows the comparisons and swaps for each pass:

• Pass 1: Compare 7 with 8. Since 7 < 8, shift 8 right. Insert 7 at position 0. List becomes [7, 8, 13, 1, -9, 4].
• Pass 2: Compare 13 with 8. 13 > 8, so no shift. List remains [7, 8, 13, 1, -9, 4].
• Pass 3: Compare 1 with 13 (shift 13 right), then with 8 (shift 8 right), then with 7 (shift 7 right). Insert 1 at position 0. List becomes [1, 7, 8, 13, -9, 4].
• Pass 4: Compare -9 with 13 (shift), 8 (shift), 7 (shift), 1 (shift). Insert -9 at position 0. List becomes [-9, 1, 7, 8, 13, 4].
• Pass 5: Compare 4 with 13 (shift), 8 (shift), 7 (shift). 4 > 1, so stop shifting. Insert 4 after 1. List becomes [-9, 1, 4, 7, 8, 13].

The final sorted list in ascending order is [-9, 1, 4, 7, 8, 13].

Algorithm

Algorithm 5.3: Insertion Sort

INSERTIONSORT(numList, n)
Step 1: SET i = 1
Step 2: WHILE i < n REPEAT STEPS 3 to 9
Step 3:   temp = numList[i]
Step 4:   SET j = i - 1
Step 5:   WHILE j >= 0 and numList[j] > temp, REPEAT STEPS 6 to 7
Step 6:     numList[j+1] = numList[j]
Step 7:     SET j = j - 1
Step 8:   numList[j+1] = temp        # insert temp at position j+1
Step 9: SET i = i + 1

Program 5-3: Implementation of insertion sort using Python.

def insertion_Sort(list3):
    n = len(list3)
    for i in range(n):
        temp = list3[i]
        j = i - 1
        while j >= 0 and temp < list3[j]:
            list3[j+1] = list3[j]
            j = j - 1
        list3[j+1] = temp

numList = [8, 7, 13, 1, -9, 4]
insertion_Sort(numList)
print("The sorted list is :")
for i in range(len(numList)): …