insertion-sort

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

• Tracing through the insertion sort involves starting at element 1 (not 0)

• i increments through each element one at a time and each item is compared to the one previous. If the previous item is bigger or equal it is set to list[position]

• If position equals 0 then the iteration is at the start of the list and the next iteration begins

Trace Table of the Insertion sort