Insertion Sort

What is an insertion sort?

• The insertion sort sorts one item at a time by placing it in the correct position of an unsorted list
• This process repeats until all items are in the correct position
• Specifically, the current item being sorted is compared to each previous item
• If it is smaller than the previous item then the previous item is moved to the right and the current item takes its place
• If the current item is larger than the previous item then it is in the correct position and the next current item is then sorted as illustrated below

Performing the insertion sort

Figure 2: Performing the Insertion sort

Time complexity of an insertion sort

• In the above algorithm, one statement is present, a for loop with three statements and a nested while loop that contains two statements
• The time complexity for the insertion sort would be 3n*2n + 1, giving 6n² + 1. 3n comes from the for loop having three statements inside it, not including the while. 2n comes from the while loop having two statements inside it
• Removing coefficients and dominated factors leaves O(n²) as the worst case scenario
• The best case scenario would be an already sorted list which means each item is checked one at a time giving a time complexity of O(n)
• The average case scenario would be a half sorted list giving O(n²/2), which when coefficients are removed still gives O(n²)

Space complexity of an insertion sort

• As the insertion sort requires no additional space, it is space complexity O(1)

Tracing an Insertion Sort

An insertion sort works by logically splitting the list into a sorted and an unsorted part. Values from the unsorted part are picked and placed into the correct position in the sorted part.

• The search starts at index $1$ (the second element), assuming the first element (index $0$) is already a “sorted” list of one.
• The item is compared to the elements to its left.
• If the element to the left is larger than the item, that element is shifted one position to the right to create a “hole.”
• This continues until a value smaller than or equal to the item is found, or the start of the list is reached.
• The item is then inserted into the “hole.”

Trace Table: [5, 9, 4, 2, 7, 1, 2, 4, 3]

Pass (i)	Item	Comparison	Action	List State after Pass
-	-	-	Initial State	[5, 9, 4, 2, 7, 1, 2, 4, 3]
1	9	$9>5$	No shift needed	[5, 9, 4, 2, 7, 1, 2, 4, 3]
2	4	$4<9$, $4<5$	Shift 9 and 5	[4, 5, 9, 2, 7, 1, 2, 4, 3]
3	2	$2<9,5,4$	Shift 9, 5, 4	[2, 4, 5, 9, 7, 1, 2, 4, 3]
4	7	$7<9$	Shift 9	[2, 4, 5, 7, 9, 1, 2, 4, 3]
5	1	$1<9,7,5,4,2$	Shift all left	[1, 2, 4, 5, 7, 9, 2, 4, 3]

---

Worked Example: Describing Insertion Sort

The following pseudocode procedure performs an insertion sort on the array parameter.

01 procedure insertionSort(dataArray:byRef)
02    for i = 1 to dataArray.Length - 1
03        temp = dataArray[i]
04        tempPos = i - 1
05        while tempPos >= 0 and dataArray[tempPos] > temp
06            dataArray[tempPos + 1] = dataArray[tempPos]
07            tempPos = tempPos - 1
08        endwhile
09        dataArray[tempPos + 1] = temp
10    next i
11 endprocedure

Question: Describe how an insertion sort will sort an array.

Answer:

1. The algorithm iterates through the list starting from the second element ($i=1$) [1].
2. The current element is stored in a temporary variable (temp) [1].
3. It compares temp with the elements in the sorted portion to its left [1].
4. If an element to the left is larger than temp, that element is shifted one position to the right (dataArray[tempPos + 1] = dataArray[tempPos]) [1].
5. This process repeats until the correct position is found or the beginning of the array is reached [1].
6. Finally, the temp value is inserted into its correct sorted position [1].

Implementing an Insertion Sort

procedure insertionSort(list)
    n = len(list)
    for i = 1 to n - 1
        item = list[i]
        position = i
        
        // Shift elements of list[0...i-1] that are greater than item
        // to one position ahead of their current position
        while position > 0 and list[position - 1] > item
            list[position] = list[position - 1]
            position = position - 1
        endwhile
        
        list[position] = item
    next i
endprocedure

• Efficiency: Insertion sort has a worst-case time complexity of $O(n^2)$, but it is very efficient for small datasets or lists that are already mostly sorted ($O(n)$ in the best case).
• The “Shift” Mechanism: Unlike Bubble Sort, which uses swaps, Insertion Sort shifts values. The line list[position] = list[position - 1] copies the larger value into the current index, effectively moving the “empty slot” to the left.
• In-Place Sorting: This algorithm is memory efficient because it sorts the list within the original array without requiring a duplicate copy of the data.

Examiner Tips and Tricks

Remember that while position moves backward from i to 0, the for loop moves forward from index 1 to the end of the list.

def insertion_sort(data):
    # Start from the second element (index 1)
    for i in range(1, len(data)):
        item = data[i]
        position = i
        
        # Compare item with elements to its left
        while position > 0 and data[position - 1] > item:
            # Shift the larger element to the right
            data[position] = data[position - 1]
            position -= 1
            
        # Insert the item into its final position
        data[position] = item
        
    return data
 
# Example Usage
my_list = [5, 9, 4, 2, 7, 1, 2, 4, 3]
sorted_list = insertion_sort(my_list)
print(sorted_list)