I wanted to make Insertion Sort part of a two-fer with Selection Sort, but it honestly took me a minute to figure out how to implement.

Continuing the card game analogy of earlier, if Selection Sort is scanning your hand and moving the smallest items down to the left, eventually ending up with a fully sorted hand…

Insertion Sort is like when a dealer gives you a new card. You look over what you’ve got so far, and add the card to its rightful spot. Similar to Selection Sort, Insertion Sort also operates on the idea of a “sorted” section and  an “unsorted” section.

When an item (let’s call it A) is larger than the element to its immediate left (B), the two aren’t swapped like in Bubble Sort. Instead, you hold on to A’s value, and then reassign B’s value to the spot array[A]. So it’s like you are sliding B’s value down the line. Then you compare A with the item in the index to the left again (C). If A > C, you can then put A down in array[B]’s original spot. Otherwise, you need to keep working to the left and shifting over elements until you find the right spot for A. When you finally assign A to its spot, you’re done with inserting A. Then you repeat the process with the next item in the “unsorted” section.

I had some issues wrapping my head around how to move items down the line, making room for the array, initially thinking about a recursive solution, but really all I needed was a while loop.