**Introduction to Insertion Sort**

5 is greater than 3 comes here next is 1 1 I keep it in a variable K then 6 is greater so 6 goes to the right 5 is greater goes to the right 3 is greater goes to the right one comes here next comes 8 8 becomes the key but 8 is greater than 6 so this whole thing is sorted right again it's moving quickly so this whole thing is sorted this is the unsorted part I take the first element in the unsorted part keep it in a variable keep moving these things and place this in the appropriate location so this will also move into welcome right. So, at any point if you are in doubt just go to the Wikipedia article look at this animation you will recall what insertions are. This is one of the best visualizations I know or I have come across for insertion sort. So, at any point if you are in doubt just go to the Wikipedia article look at this animation you will recall what insertions are. Very very simple algorithm and I strongly recommend if anyone of you comes across good animations or good resources like this please put them in the comment section of this video or the other students and instructors and mentors can also benefit. Right of course, I am NOT the best guy who can pick the best resources I'm sure students can pick up some brilliant resources like this right now.

**Insertion Sort Animation**

Let's go to a slightly more practical thing okay so this is a so what again as you might already know I use a Google image search a lot right. So, what I type here is I type cards insertion sort on Google Images. This is Google image search right. One of the one of the stuff that I get here is this nice nice photograph of a person holding a pack of cards or a small set of cards and this is from the Emory University in the math and computer science department right now if you notice when you're sorting a pack of cards suppose I have the eighth element if you look at this this is my sorted sub-array okay let me change the colors here. This is my sorted sub-array eye, the next element that I want to insert I will insert it I'll try to insert the next element into the place where it should belong to right so this the reason the name insert insertion sort is because this is equivalent to taking a set of cards and inserting the right card see when you sort when you sought a bunch of cards that you have right you come from left to right you pick a card you insert it at the right position like for example eight is being inserted here between seven and K because that's where it should belong to right. Where this is my sorted sub and this is already my sorted sub-array right this whole thing is my sorted sub we're including K including K this is my sorted sub-array like let's say let's assume in my unsorted sub R let's say you in the next element is a so I pick up the card date and place it exactly where it should belong so I am picking up a card from the unsorted area or unsorted sub-array and I am inserting it the word insert is input I am inserting it in the right location. So, next time when you are sorting a pack of cards like this you should remember about any sessions on what you are actually doing when you are trying to insert each of these cards into their appropriate locations is you're performing insertion sort without even knowing the name insertion sort right.

**Practical Application of Insertion Sort**

So, whenever you pick a pack of cards remember what you're doing is insertion sort right very very simple concept nothing fancy this is one of the simplest sorting algorithms trust me extremely simple extremely easy to understand in a nutshell you have a sorted array. Oh by the way there is a small interesting twist I wanted to mention at the start what's happening you have only one element which is sorted rest everything is your unsorted array and the first iteration at the very first iteration you have only one array with only one element which is sorted rest everything is unsorted that's where you're picking the second element which is the first element in the unsorted array obviously if you have only one element right if you have an array with only one element it is trivially sorted because there's nothing else to sort right. So, at the start of all the AI trations is important at the start of all the iterations only your first item in the array is sorted rest everything is unsorted trivially now you take each of these elements or you take the first element in the unsorted array try to place it in the sorted sub that this becomes clearer as we go forward but what happens at the start the first element is the trivially unsorted array right because if you have an array with only one element it's obviously sorted right so the next element in the unsorted array let's assume this whole thing is unsorted array the next element in unsorted array we will try to insert into this sorted pot and so that's how this insertion sort works.

**Conclusion**

In conclusion, insertion sort is a simple yet efficient sorting algorithm that uses the concept of inserting elements into their correct positions within an already sorted sub-array. It is an excellent visualization tool for understanding the basics of sorting algorithms, and its simplicity makes it accessible to beginners and experts alike. By following these steps and watching the animation provided in this video, you should be able to understand how insertion sort works and appreciate its beauty and simplicity.

"WEBVTTKind: captionsLanguage: enokay folks now let's actually dive into the insertion sort algorithm itself right so let's take an array a okay just for simplicity okay of course first we'll understand the intuition before we dive into the code because understanding the intuition is much more important because if once you know the intuition once you know how insertion sort works writing code is just a simple extension to it right so I'll take a simple example imagine I have a an array of values six five three okay three one eight seven two and four okay this is my unsorted array right this is my unsorted array now let's say Hume I want to sort this okay now let's let's understand the intuition behind insertion start step by step then we will see a nice animation so that you will always remember it right first I will explain it to you as if I'm explaining it to you and in blackboard or whiteboard okay now let's go step by step first thing that I will do here is look at this first element okay this element is just six let's not touch it let's start from the second element let us say pick up this element five right now when I say I want to sort it by default it means ascending order the default order for all sorting is ascending order if not mention otherwise if it is clearly stated yes sorted in descending order that's a different thing if I if you don't say anything it means ascending order now let's look at just let's say the second element here which is 5 now this 5 is smaller than 6 so in the final sorted array if you think about it in the final sorted array this element 5 or key 5 should be on the left hand side of 6 right because we want the array to be an ascending order right in the final array imagine in the sorted array this 5 should be it should be like this right in the final array this 5 should be on the left side of 6 not on the right side in the final sorted array so let's let's let's do it this way okay because because we understand this property now we compare 5 with 6 okay so we are comparing so we have taken the second element this is the first element second and third element fourth element v element sixth seventh eighth of course in some programming languages like C or Java you might call this as a zeroth element first element second element third element etc I'll just keep it simple okay let's call this the first element because it's much more easy to think about instead of thinking of it as zeroth element right so now let's take the five which is the second element so I start with the second element I compare it with the first element here first thing you'll notice is that five should be on this side and six should be on this side so first thing is I'll push so I'll take five into some variable let's call that variable as K okay I will first copy five into a variable five into a variable K okay I'll keep this here now I look at six now first thing that I'll notice is that five should be on the left side of six so I will move six to the right okay so what will I do I'll move six to the right here I'm not touching the rest of the array if you notice I am not touching the rest of the array the rest of the array is as is I have not touched it at all okay let's just put a comma here okay instead of drawing these boxes I'm just placing a comma so the rest of the erase this part I'm not touching it at all I have just placed the second element in a variable called K right I've compared this K with six I noticed that six is larger which means six should be pushed to the right so I move six to the right there is no more element here there is nothing else here so I place five here right so my second element is taken care of this is my first iteration right first thing you have to notice here is the moment I finished this this sub array I have two sub arrays right this is a sub array that I have already processed this is an sub array that I have not touched by sub array I mean a conscious ette a subset of the array which is sequential right this whole part if you look at this this is one sub array this is one sub array okay so this sub array already looks sorted if you notice here this five and six they are in a sorted order this whole thing which have not yet touched this sub is not yet in the sorted order right so let's let's draw these boxes so that it becomes clearer for you okay I'll just draw these boxes okay so 5 6 3 1 8 7 2 4 so this sub array right now looks sorted this sub array only this part this rest of this part rest of this part we haven't touched it yet okay so we have processed the second element very good now let's go to the third element okay now when I go to the third element what will I do okay now let's take of course I'll change my K now my K becomes 3 because I'm looking at the third element here I'm looking at this element now I will say look at this 3 3 is what I'm copying into a variable called okay now I will compare this 3 with 6 3 should be on the left side of 6 ok because 3 should be on the left side of 6 let's push 6 to the right okay so we'll get 6 here the rest of the sub-array I am not touching 1 8 7 2 4 I am not touching this sub area I am not at all touching this ok so because 3 is less than 6 I push 6 to the right okay I've copied this 3 here so even if I overwrite this 3 that's okay because I have stored this 3 in a variable called K right this 6 is gone to the right now let's take the next element so the 6 is processed now what about 5 5 is also greater than 3 so we should push 5 also so we push 5 also to the right now what is left only 3 is left there is no more there are no more elements to the left of it right so we place the value 3 here now if you notice because we have processed the third element now look at this in the first iteration we process the second element in the second iteration we process the third element because we have process to the third element if you notice carefully this sub array till the third element is already sorted this is the perfect solid order 3 less than equal to 5 less than equal to 6 when this sub still not touched we haven't yet touched it right fair enough so we have processed the third element and by the time we process the third element the first three elements in the array are perfectly sorted right so let's let's go to the next step okay I'll just erase this I'll just erase this so that we can see the whole story going on here itself now this is the array that I have let me just draw a box around it okay so first element second element third element fourth fifth six seven eight now let's take the fourth element because we've already processed the second element and the third element now let's go to the fourth element okay so when I go to the fourth element let me change the colors here when they go to the fourth element okay I'll store the fourth element in a variable K so k equals to one now now this one is less than six which means six should be pushed to the right okay we will not touch this sub array the sub array will just keep it as is 8 7 2 4 we will just keep this sub array as is let's not touch it the rest of the sub array till the fourth element we'll play around with it now k equals to 1 is what I am comparing everything against now 6 is greater than 1 so 6 should get pushed to the right right so 6 will come here now 6 is already taken care of next element is 5 now compare our K with 5 right K is less than 5 so push K push 5 also to the right so I have pushed 5 to the right next take the next element so this is processed next element 3 right compare K with 3 K is less than 3 so push K sorry push 3 to the right so I've pushed 3 to the right no more elements to be compared with nothing else here there is nothing else here so I paste 1 at this place now if you again notice these first four elements are now in the sorted order these rest we haven't yet touched them we haven't yet touched the next four elements okay next K becomes 8 the next element right because you process the second see we have processed the second element here and reached here we have processed the third element and reached here then we have processed the fourth element and reached here now let's process the fifth element now if you think intuitively look at this I keep my k equals to 8 now whatever value so 6 now let's look at the 6 right we know that this sub array is already sorted if you notice that so we are that's how we are constructing it right now I compare 8 with 6 8 is greater than 6 which means I need not push my 6 to the right I can keep everything as is because I know that this array is already sorted I already know that this element is the largest element so by comparing 8 with 6 because 8 is larger than 6 I don't have to compare 8 with 5 3 1 now I don't have to compare my K with the third element second element and first element because my K whatever value that I have in K is greater than the fourth element itself so I don't even compare so the moment I realized that 8 is greater than or K my value whatever I have in K is greater than this element I stop there I leave it as is no more moving to the right no more swapping no more moving to the right so my array at the end of the fifth iteration will look like this 1 3 5 6 8 these are all sorted my 7 2 4 are not sorted so this sub array is now sorted this sub array is not sorted right now so first five elements are sorted now let's go to the sixth element okay let's go to the sixth element which is 7 now so my K now my K becomes 7 now I compare 7 with 8 because that's what I have right in my key in my key I have 7 I compare my K or key with with 8 here ok 8 is greater which means 8 should move to the right right so now what do I have I have 1 3 5 6 I haven't touched this I have something empty here I have 8 here I have 8 to 4 my K is still here so I've come I've moved this to the right all right now I compare my K with six my K is greater than six which means six need not move to the right because whatever I have in K is larger than or equal to six right so I don't have to move it because this is smaller than or equal to K I don't have to test with rest of these elements because I know that they are already in sorted order till here right so I will insert my seven here now what happened the elements still here are sorted and these are unsorted now I'll take K equals to two I'll compare K now K becomes two I'll compare this with eight K is less than eight K is less than seven so this thing gets pushed this thing gets pushed this thing gets pushed this thing gets pushed this thing gets pushed so this thing gets pushed the here it stops now what happens to my sorted array I would get again let me just write here okay I would get one two three five seven eight four right now this is my sorted sub-array this is my unsorted submarine now again K becomes fourth I start comparing K with this eight is greater so it should move to the right 7 is greater so it should move to the right five is greater so it should move to the right three is less than equal to so three need not worry about it right so what will happen of one two three four five seven eight is there six somewhere I think I missed the six on there right okay there should be six here sorry there should be six here I'm sorry five six seven eight right so if you look at it what are we doing here at any iteration look at this I tration for example we have a sort of intuitively now let's try to think about this intuitively because that will build the build the muscle build the Builder intuition so we have a sorted sub-array we have the next element in the array that we take now we try to insert this into the sorted sub-array in the appropriate location like even here look at look at what's happening this is a sorted sub-array we have a sorted sub-array right this whole thing is a sorted sub-array I take the next value in the array now I try to insert this into the sorted sub-array at the appropriate location by moving all elements greater than that to the right that is why the name insertion sort because at every iteration you are picking up the first element in the unsorted array and you are inserting it in the appropriate location in the sorted array that's why it's called insertion sort okay I hope this flow is simple I'll show you some very nice animation okay so if you go to wiki tip if you go to the Wikipedia article say I am on the Wikipedia article for insertion sort again we keep it has a phenomenal source I mean I I learn a lot of new things from Wikipedia in addition to all the textbooks Wikipedia is the world's best resource to learn data structures and algorithms right I'm on the Wikipedia page for insertion sort like if you go slightly down there is a section called algorithm where there is this nice animation I've actually taken this example look at this this is already sorted this is unsorted array I start with first element first element stays the same next I go to the second element here I keep the second element in a variable 5 because 6 is greater I pushed it to the right placed 5 next element is 3 right I keep 3 in a in a variable 6 is greater 5 is greater 3 comes here next is 1 1 I keep it in a variable K then 6 is greater so 6 goes to the right 5 is greater goes to the right 3 is greater goes to the right one comes here next comes 8 8 becomes the key but 8 is greater than 6 so so if you notice at any point this whole thing is sorted right again it's moving quickly so this whole thing is sorted this is the unsorted part I take the first element in the unsorted part keep it in a variable keep moving these things and place this in the appropriate location so this will also move into welcome right so this animation is one of the best visualizations I know or I have come across for insertion sort so at any point if you are in doubt just go to the Wikipedia article look at this animation you will recall what insertions are this right very very simple algorithm and I strongly recommend if anyone of you comes across good animations or good resources like this please put them in the comment section of this videos or the other students and instructors and mentors can also benefit right of course I am NOT the best guy who can pick the best resources I'm sure students can pick up some brilliant resources like this right now let's go to a slightly more practical thing okay so this is a so what again as you might already know I use a google image search a lot right so what I type here is I type cards insertion sort on Google Images this is Google image search right so one of the one of the stuff that I get here is this nice nice photograph of a person holding a pack of cards or a small set of cards and this is from the Emory University in the math and computer science department right now if you notice when you're sorting a pack of cards suppose I have the eighth element if you look at this this is my sorted sub-array okay let me change the colors here this is my sorted sub-array eye the next element that I want to insert I will insert it I'll try to insert the next element into the place where it should belong to right so this the reason the name insert insertion sort is because this is equivalent to taking a set of cards and inserting the right card see when you sort when you sought a bunch of cards that you have right you come from left to right you pick a card you insert it at the right position like for example eight is being inserted here between seven and K because that's where it should belong to right where this is my sorted sub and this is already my sorted sub-array right this whole thing is my sorted sub we're including K including K this is my sorted sub-array like let's say let's assume in my unsorted sub R let's say you in the next element is a so I pick up the car date and place it exactly where it should belong so I am picking up a card from the unsorted area or unsorted sub-array and I am inserting it the word insert is input I am inserting it in the right location so next time when you are sorting a pack of cards like this you should remember about any sessions on what you are actually doing when you are trying to insert each of these cards into their appropriate locations is you're performing insertion sort without even knowing the name insertion sort right so whenever you pick a pack of cards remember what you're doing is insertion sort right very very simple concept nothing fancy this is one of the simplest sorting algorithms trust me extremely simple extremely easy to understand in a nutshell you have a sorted array oh by the way there is a small interesting twist I wanted to mention at the start what's happening you have only one element which is sorted rest everything is your unsorted array and the first iteration at the very first iteration you have only one array with only one element which is sorted rest everything is unsorted that's where you're picking the second element which is the first element in the unsorted array obviously if you have only one element right if you have an array with only one element it is trivially sorted because there's nothing else to sort right so at the start of all the AI trations is important at the start of all the iterations only your first item in the array is sorted rest everything is unsorted trivially now you take each of these elements or you take the first element in the unsorted array try to place it in the sorted sub that this becomes clearer as we go forward but what happens at the start the first element is the trivially unsorted array right because if you have an array with only one element it's obviously sorted right so the next element in the unsorted array let's assume this whole thing is unsorted array the next element in unsorted array we will try to insert into this sorted pot and so that's how this insertion sort works intuitivelyokay folks now let's actually dive into the insertion sort algorithm itself right so let's take an array a okay just for simplicity okay of course first we'll understand the intuition before we dive into the code because understanding the intuition is much more important because if once you know the intuition once you know how insertion sort works writing code is just a simple extension to it right so I'll take a simple example imagine I have a an array of values six five three okay three one eight seven two and four okay this is my unsorted array right this is my unsorted array now let's say Hume I want to sort this okay now let's let's understand the intuition behind insertion start step by step then we will see a nice animation so that you will always remember it right first I will explain it to you as if I'm explaining it to you and in blackboard or whiteboard okay now let's go step by step first thing that I will do here is look at this first element okay this element is just six let's not touch it let's start from the second element let us say pick up this element five right now when I say I want to sort it by default it means ascending order the default order for all sorting is ascending order if not mention otherwise if it is clearly stated yes sorted in descending order that's a different thing if I if you don't say anything it means ascending order now let's look at just let's say the second element here which is 5 now this 5 is smaller than 6 so in the final sorted array if you think about it in the final sorted array this element 5 or key 5 should be on the left hand side of 6 right because we want the array to be an ascending order right in the final array imagine in the sorted array this 5 should be it should be like this right in the final array this 5 should be on the left side of 6 not on the right side in the final sorted array so let's let's let's do it this way okay because because we understand this property now we compare 5 with 6 okay so we are comparing so we have taken the second element this is the first element second and third element fourth element v element sixth seventh eighth of course in some programming languages like C or Java you might call this as a zeroth element first element second element third element etc I'll just keep it simple okay let's call this the first element because it's much more easy to think about instead of thinking of it as zeroth element right so now let's take the five which is the second element so I start with the second element I compare it with the first element here first thing you'll notice is that five should be on this side and six should be on this side so first thing is I'll push so I'll take five into some variable let's call that variable as K okay I will first copy five into a variable five into a variable K okay I'll keep this here now I look at six now first thing that I'll notice is that five should be on the left side of six so I will move six to the right okay so what will I do I'll move six to the right here I'm not touching the rest of the array if you notice I am not touching the rest of the array the rest of the array is as is I have not touched it at all okay let's just put a comma here okay instead of drawing these boxes I'm just placing a comma so the rest of the erase this part I'm not touching it at all I have just placed the second element in a variable called K right I've compared this K with six I noticed that six is larger which means six should be pushed to the right so I move six to the right there is no more element here there is nothing else here so I place five here right so my second element is taken care of this is my first iteration right first thing you have to notice here is the moment I finished this this sub array I have two sub arrays right this is a sub array that I have already processed this is an sub array that I have not touched by sub array I mean a conscious ette a subset of the array which is sequential right this whole part if you look at this this is one sub array this is one sub array okay so this sub array already looks sorted if you notice here this five and six they are in a sorted order this whole thing which have not yet touched this sub is not yet in the sorted order right so let's let's draw these boxes so that it becomes clearer for you okay I'll just draw these boxes okay so 5 6 3 1 8 7 2 4 so this sub array right now looks sorted this sub array only this part this rest of this part rest of this part we haven't touched it yet okay so we have processed the second element very good now let's go to the third element okay now when I go to the third element what will I do okay now let's take of course I'll change my K now my K becomes 3 because I'm looking at the third element here I'm looking at this element now I will say look at this 3 3 is what I'm copying into a variable called okay now I will compare this 3 with 6 3 should be on the left side of 6 ok because 3 should be on the left side of 6 let's push 6 to the right okay so we'll get 6 here the rest of the sub-array I am not touching 1 8 7 2 4 I am not touching this sub area I am not at all touching this ok so because 3 is less than 6 I push 6 to the right okay I've copied this 3 here so even if I overwrite this 3 that's okay because I have stored this 3 in a variable called K right this 6 is gone to the right now let's take the next element so the 6 is processed now what about 5 5 is also greater than 3 so we should push 5 also so we push 5 also to the right now what is left only 3 is left there is no more there are no more elements to the left of it right so we place the value 3 here now if you notice because we have processed the third element now look at this in the first iteration we process the second element in the second iteration we process the third element because we have process to the third element if you notice carefully this sub array till the third element is already sorted this is the perfect solid order 3 less than equal to 5 less than equal to 6 when this sub still not touched we haven't yet touched it right fair enough so we have processed the third element and by the time we process the third element the first three elements in the array are perfectly sorted right so let's let's go to the next step okay I'll just erase this I'll just erase this so that we can see the whole story going on here itself now this is the array that I have let me just draw a box around it okay so first element second element third element fourth fifth six seven eight now let's take the fourth element because we've already processed the second element and the third element now let's go to the fourth element okay so when I go to the fourth element let me change the colors here when they go to the fourth element okay I'll store the fourth element in a variable K so k equals to one now now this one is less than six which means six should be pushed to the right okay we will not touch this sub array the sub array will just keep it as is 8 7 2 4 we will just keep this sub array as is let's not touch it the rest of the sub array till the fourth element we'll play around with it now k equals to 1 is what I am comparing everything against now 6 is greater than 1 so 6 should get pushed to the right right so 6 will come here now 6 is already taken care of next element is 5 now compare our K with 5 right K is less than 5 so push K push 5 also to the right so I have pushed 5 to the right next take the next element so this is processed next element 3 right compare K with 3 K is less than 3 so push K sorry push 3 to the right so I've pushed 3 to the right no more elements to be compared with nothing else here there is nothing else here so I paste 1 at this place now if you again notice these first four elements are now in the sorted order these rest we haven't yet touched them we haven't yet touched the next four elements okay next K becomes 8 the next element right because you process the second see we have processed the second element here and reached here we have processed the third element and reached here then we have processed the fourth element and reached here now let's process the fifth element now if you think intuitively look at this I keep my k equals to 8 now whatever value so 6 now let's look at the 6 right we know that this sub array is already sorted if you notice that so we are that's how we are constructing it right now I compare 8 with 6 8 is greater than 6 which means I need not push my 6 to the right I can keep everything as is because I know that this array is already sorted I already know that this element is the largest element so by comparing 8 with 6 because 8 is larger than 6 I don't have to compare 8 with 5 3 1 now I don't have to compare my K with the third element second element and first element because my K whatever value that I have in K is greater than the fourth element itself so I don't even compare so the moment I realized that 8 is greater than or K my value whatever I have in K is greater than this element I stop there I leave it as is no more moving to the right no more swapping no more moving to the right so my array at the end of the fifth iteration will look like this 1 3 5 6 8 these are all sorted my 7 2 4 are not sorted so this sub array is now sorted this sub array is not sorted right now so first five elements are sorted now let's go to the sixth element okay let's go to the sixth element which is 7 now so my K now my K becomes 7 now I compare 7 with 8 because that's what I have right in my key in my key I have 7 I compare my K or key with with 8 here ok 8 is greater which means 8 should move to the right right so now what do I have I have 1 3 5 6 I haven't touched this I have something empty here I have 8 here I have 8 to 4 my K is still here so I've come I've moved this to the right all right now I compare my K with six my K is greater than six which means six need not move to the right because whatever I have in K is larger than or equal to six right so I don't have to move it because this is smaller than or equal to K I don't have to test with rest of these elements because I know that they are already in sorted order till here right so I will insert my seven here now what happened the elements still here are sorted and these are unsorted now I'll take K equals to two I'll compare K now K becomes two I'll compare this with eight K is less than eight K is less than seven so this thing gets pushed this thing gets pushed this thing gets pushed this thing gets pushed this thing gets pushed so this thing gets pushed the here it stops now what happens to my sorted array I would get again let me just write here okay I would get one two three five seven eight four right now this is my sorted sub-array this is my unsorted submarine now again K becomes fourth I start comparing K with this eight is greater so it should move to the right 7 is greater so it should move to the right five is greater so it should move to the right three is less than equal to so three need not worry about it right so what will happen of one two three four five seven eight is there six somewhere I think I missed the six on there right okay there should be six here sorry there should be six here I'm sorry five six seven eight right so if you look at it what are we doing here at any iteration look at this I tration for example we have a sort of intuitively now let's try to think about this intuitively because that will build the build the muscle build the Builder intuition so we have a sorted sub-array we have the next element in the array that we take now we try to insert this into the sorted sub-array in the appropriate location like even here look at look at what's happening this is a sorted sub-array we have a sorted sub-array right this whole thing is a sorted sub-array I take the next value in the array now I try to insert this into the sorted sub-array at the appropriate location by moving all elements greater than that to the right that is why the name insertion sort because at every iteration you are picking up the first element in the unsorted array and you are inserting it in the appropriate location in the sorted array that's why it's called insertion sort okay I hope this flow is simple I'll show you some very nice animation okay so if you go to wiki tip if you go to the Wikipedia article say I am on the Wikipedia article for insertion sort again we keep it has a phenomenal source I mean I I learn a lot of new things from Wikipedia in addition to all the textbooks Wikipedia is the world's best resource to learn data structures and algorithms right I'm on the Wikipedia page for insertion sort like if you go slightly down there is a section called algorithm where there is this nice animation I've actually taken this example look at this this is already sorted this is unsorted array I start with first element first element stays the same next I go to the second element here I keep the second element in a variable 5 because 6 is greater I pushed it to the right placed 5 next element is 3 right I keep 3 in a in a variable 6 is greater 5 is greater 3 comes here next is 1 1 I keep it in a variable K then 6 is greater so 6 goes to the right 5 is greater goes to the right 3 is greater goes to the right one comes here next comes 8 8 becomes the key but 8 is greater than 6 so so if you notice at any point this whole thing is sorted right again it's moving quickly so this whole thing is sorted this is the unsorted part I take the first element in the unsorted part keep it in a variable keep moving these things and place this in the appropriate location so this will also move into welcome right so this animation is one of the best visualizations I know or I have come across for insertion sort so at any point if you are in doubt just go to the Wikipedia article look at this animation you will recall what insertions are this right very very simple algorithm and I strongly recommend if anyone of you comes across good animations or good resources like this please put them in the comment section of this videos or the other students and instructors and mentors can also benefit right of course I am NOT the best guy who can pick the best resources I'm sure students can pick up some brilliant resources like this right now let's go to a slightly more practical thing okay so this is a so what again as you might already know I use a google image search a lot right so what I type here is I type cards insertion sort on Google Images this is Google image search right so one of the one of the stuff that I get here is this nice nice photograph of a person holding a pack of cards or a small set of cards and this is from the Emory University in the math and computer science department right now if you notice when you're sorting a pack of cards suppose I have the eighth element if you look at this this is my sorted sub-array okay let me change the colors here this is my sorted sub-array eye the next element that I want to insert I will insert it I'll try to insert the next element into the place where it should belong to right so this the reason the name insert insertion sort is because this is equivalent to taking a set of cards and inserting the right card see when you sort when you sought a bunch of cards that you have right you come from left to right you pick a card you insert it at the right position like for example eight is being inserted here between seven and K because that's where it should belong to right where this is my sorted sub and this is already my sorted sub-array right this whole thing is my sorted sub we're including K including K this is my sorted sub-array like let's say let's assume in my unsorted sub R let's say you in the next element is a so I pick up the car date and place it exactly where it should belong so I am picking up a card from the unsorted area or unsorted sub-array and I am inserting it the word insert is input I am inserting it in the right location so next time when you are sorting a pack of cards like this you should remember about any sessions on what you are actually doing when you are trying to insert each of these cards into their appropriate locations is you're performing insertion sort without even knowing the name insertion sort right so whenever you pick a pack of cards remember what you're doing is insertion sort right very very simple concept nothing fancy this is one of the simplest sorting algorithms trust me extremely simple extremely easy to understand in a nutshell you have a sorted array oh by the way there is a small interesting twist I wanted to mention at the start what's happening you have only one element which is sorted rest everything is your unsorted array and the first iteration at the very first iteration you have only one array with only one element which is sorted rest everything is unsorted that's where you're picking the second element which is the first element in the unsorted array obviously if you have only one element right if you have an array with only one element it is trivially sorted because there's nothing else to sort right so at the start of all the AI trations is important at the start of all the iterations only your first item in the array is sorted rest everything is unsorted trivially now you take each of these elements or you take the first element in the unsorted array try to place it in the sorted sub that this becomes clearer as we go forward but what happens at the start the first element is the trivially unsorted array right because if you have an array with only one element it's obviously sorted right so the next element in the unsorted array let's assume this whole thing is unsorted array the next element in unsorted array we will try to insert into this sorted pot and so that's how this insertion sort works intuitively\n"