People use “sort” in many different programs; it is a primary function when it comes to organizing a list. Due to its wide uses, the adequate sorting algorithm that sufficiently performs the given function is very important. Insertion sort is one of those sorting algorithms that is used in several programs.
Insertion sort is simple because it works just like “the way [one sorts] playing cards.”1 Basically, starting from the second element, it sets a single element as a key. This key is then compared with the previous elements, moving one place up if it is smaller than the previous. When this whole step is repeated for each key, the array would be sorted. In step-to-step order, it looks like this:
- Starting from the second element, set the element as the “key”
- Compare the key with the previous element
- If the key is smaller than the previous, move it one place up
- Repeat step 2-3 until the key has no bigger element in the front
- Repeat the whole step, setting the next elements as the next “key”
In C++, it looks like this2:
Despite this simplistic structure, insertion sort is quite inefficient in time-complexity wise.3 In the best case where the elements are already sorted, comparison will only happen once per the key. This will make the time complexity O(n), with n being the number of elements in the array. In the worst case where the elements are sorted in reverse order – such as, in descending order while the program wants it in ascending order – each element will be compared with every other, making the time complexity O(n2). This will have a similar effect on most of the arrays where the elements are placed in neither ascending nor descending, but rather in jumbled order, making the average time complexity to be O(n2) too.
Time and space efficiency is an important factor during programming. Thus it makes insertion sort, which is not as time efficient as other sorting algorithms such as heap sort or merge sort, not a perfect option in that perspective. If the list contains lots of elements, it will consume an extreme amount of time.3 However, the fact that it is simple makes the insertion sort a good option when one is beginning to learn about the sorting algorithms, or when most of the elements are already in correct order. For example, it will be greatly useful in fields such as benchmark studies.4 Just like any other algorithms, the insertion sort has its advantages and disadvantages; the important thing is to know where it can be used efficiently and use it in such places.
