Insertion Sort





Definition: A process designed to sort an unordered set of linear data into either ascending order (lowest to highest) or descending order (highest to lowest). This is done by taking one element at a time (starting from the second element) and shifting it leftwards until it is in the designated order with all elements to the left of its initial position. This involves moving any element that is passed by the shifted element to the right one spot in order to create room for insertion. See an example of the procedure below.


Procedure for ASCENDING Insertion Sort:

  1. Locate the second element. Compare it to the value left of it, swapping elements if needed to get the first two elements into ascending order.
  2. Repeat step 1 but with the third element and the two elements to the left of it, inserting where proper in the already sorted part of the list.
  3. Do the same for the fourth, fifth, and sixth elements, sliding them leftwards (and the elements it passes over rightwards) until they are inserted into the correct spot.





Fun Fact #1: The theory behind insertion sort is used to implement shell sort, another popular (and more efficient) sorting algorithm.

Fun Fact #2: Similar to selection sort, insertion sort is extremely slow for large datasets.



Commonly Used In: