Notes
The insertion sort take the element one by one in the order they existed in a list and then put it in the correct spot in the sort list; it repeats until no more number in the unsorted list.
Example (Using Two Lists)
Unsorted: 6, 8, 5, 7, 2, 4 Take the number in the front, in this case 6.
Sorted:
Unsorted: 8, 5, 7, 2, 4 Put it in the correct place in the sorted list. Since there is no element in the sorted list at this point, we can just put it down.
Sorted: 6
Unsorted: 8, 5, 7, 2, 4 Again, take the number in the front, in this case 8.
Sorted: 6
Unsorted: 5, 7, 2, 4 Put it in the correct place in the sorted list. Since 8 is larger than 6, so it is put to the right of 6.
Sorted: 6, 8
Unsorted: 5, 7, 2, 4 Again, take the number in the front, in this case 5.
Sorted: 6, 8
Unsorted: 7, 2, 4 Put it in the correct place in the sorted list. Since 5 is less than 6, so it is put to the left of 6.
Sorted: 5, 6, 8
Unsorted: 7, 2, 4 Again, take the number in the front, in this case 7.
Sorted: 5, 6, 8
Unsorted: 2, 4 Put it in the correct place in the sorted list. Since 7 is greater than 6 and less than 8, so it is put to the right of 6 and to the left of 8.
Sorted: 5, 6, 7, 8
Unsorted: 2, 4 Again, take the number in the front, in this case 2.
Sorted: 5, 6, 7, 8
Unsorted: 4 Put it in the correct place in the sorted list. Since 2 is less than 5, so it is put to the left of 5.
Sorted: 2, 5, 6, 7, 8
Unsorted: 4 Again, take the number in the front, in this case 4.
Sorted: 2, 5, 6, 7, 8
Unsorted: Put it in the correct place in the sorted list. Since 4 is greater than 2 and less than 5, so it is put to the right of 2 and to the left of 5.
Sorted: 2, 4, 5, 6, 7, 8
Example (Using One List)
We do not really need two list to use insertion sort, we can just use one list, but divide the list into two sections. One section is the sorted (left side), the other section is the unsorted (right side). We will use the " | " symbol to show the division between the sorted and unsorted section.
| 6, 8, 5, 7, 2, 4 Take the front number from the unsorted list, in this case 6.
6 | 8, 5, 7, 2, 4 Put it in the correct place in the sorted list. Since there is no element in the sorted list at this point, we can just put it down.
6 | 8, 5, 7, 2, 4 Again, take the front number from the unsorted list, in this case 8.
6, 8 | 5, 7, 2, 4 Put it in the correct place in the sorted list. Since 8 is larger than 6, so it is put to the right of 6.
6, 8 | 5, 7, 2, 4 Again, take the front number from the unsorted list, in this case 5.
5, 6, 8 | 7, 2, 4 Put it in the correct place in the sorted list. Since 5 is less than 6, so it is put to the left of 6.
5, 6, 8 | 7, 2, 4 Again, take the front number from the unsorted list, in this case 7.
5, 6, 7, 8 | 2, 4 Put it in the correct place in the sorted list. Since 7 is greater than 6 and less than 8, so it is put to the right of 6 and to the left of 8.
5, 6, 7, 8 | 2, 4 Again, take the front number from the unsorted list, in this case 2.
2, 5, 6, 7, 8 | 4 Put it in the correct place in the sorted list. Since 2 is less than 5, so it is put to the left of 5.
2, 5, 6, 7, 8 | 4 Again, take the front number from the unsorted list, in this case 4.
2, 4, 5, 6, 7, 8 | Put it in the correct place in the sorted list. Since 4 is greater than 2 and less than 5, so it is put to the right of 2 and to the left of 5.
Sample Code in Python
#Sorting the list [6, 8, 5, 7, 2, 4] in ascending order
list1 = [6, 8, 5, 7, 2, 4]
def insertion_sort(sort_list):
list_length = len(sort_list)
#we will start from the first element because we can just put the first element directly in the sorted section.
for i in range(1, list_length):
current_num = sort_list[i]
for j in range(i):
if sort_list[j] > current_num:
del sort_list[i]
sort_list.insert(j, current_num)
break
insertion_sort(list1)
print(list1)