What is Insertion Sort Algorithm in Data Structures

In this video, you will learn about insertion sort and its functionalities. Let’s look at what it is.

Video Transcript

When evaluating the efficiency of an algorithm, we have focused mainly on how many steps the algorithm would take, considering only the worst case scenario. This was done keeping in mind that you prepared for the worst, you will be fine in most of the cases. However, we will discover in this video that at times we need to think beyond the worst case to different between two algorithms with the same big O. This is an important skill that can help you choose an appropriate algorithm for every situation. In the previous video we learned that selection sort has an efficiency of order and square insertion. Sort will also turn out to have the same efficiency in terms of big O, but it is generally considered to be the more efficient it then selection sort. 

Video Recap

• Algorithm efficiency is evaluated by considering worst-case scenario and number of steps taken

• Thinking beyond worst case is necessary to differentiate between algorithms with same big (O)

• This skill helps in choosing appropriate algorithm for each situation

• Selection sort and insertion sort have same efficiency in terms of big(O)

• However, insertion sort is generally considered to be more efficient than selection sort.

In the next video, Aishwarya shall explain you how insertion sort works. Let's get started.

In case you are still a bit unsure on how this algorithm works, here is another video where Aishwarya explains it with another example.

As discussed , in insertion sort, you compare an element with the element to its left. If the element to its left is greater, you should shift the greater element to the right by one position and the smaller one to the left. In the next iteration, you need to compare this smaller element with the one to its left, and shift it if the element to the left is greater. You stop when you find that the element to the left is smaller than the element you are comparing with.