Insertion Sort - Eishaaya/GMRDataStructuresTest GitHub Wiki

Sorting by inserting

Imagine you have a mixed deck of cards faced down on a table. You want to sort the cards by taking a card from the top and placing it in ascending order from left to right. As you take the card you start from the right end, move the cards towards the left end, and inserting it in the correct position. This is essentially what insertion sort does. You pick out an element in your list and compare it to everything on its left one by one. If the number is greater than your current element, you move that number a position over to the left, filling in the “empty space” created by plucking out the current element. Think of an insertion sort as a selection sort that calls bubble sort until the out of order element is in the right place.

Applications:

Insertion sort is often used when the data is nearly sorted. For example, suppose you are trying sort an array in ascending order. If the current value to be inserted is greater than the value to its left, insertion sort leaves it alone and skips the inner loop entirely. Due to this characteristic, insertion sort is considered to be an adaptive algorithm, meaning that it performs operations only when necessary. Insertion sort is also a stable sorting algorithm, as the elements bubble to the correct position in the sorted section, the original relative order of equal elements are maintained.

Try and Implement this sort on your own! Look at the link in the footer for a visualizer if you need it (also to make sure your solution is actually an insertion sort)

References

  • Take a look at our implementation if you are stuck.

<-- Previous | Next -->