Insertion sort

The insertion sort is one of the most commonly used sorting algorithms used in computer programming. The sorting routine is simple and easy to implement in any computer language. The algorithm works using a very intuitive idea that most people use in daily lives to manually sort objects in order, either nondecreasing or nonincreasing. Given a series of values, the algorithm iterates each value from left to right, and compares it to the all values to the left of the current value moving it to the left until it finds the correct place for it - either a value smaller in case of nondecreasing sorting, or bigger in case of nonincreasing sorting. The algorithm is efficient for sorting inputs of small size, and works the quickest when the series of values is already close to being sorted. The algorithm performs the sort in-place.

Pseudocode

The counter variables in this pseudocode are 0-based.

    for x = 1 to len(Vals[])                                     //start at the second value (because the first one is already "sorted")
         nextval = Vals(x)                                       //retrieve the next value from the series
         y = x - 1                                               //create a counter variable to store the position of the next value to be compared
         while y > -1 and Vals(x) > nextval                      //go through all the values to left and compare, the inequality sign will
                                                                 //vary based upon the sorting type (nondecreasing or nonincreasing)
               Vals(y + 1) = Vals(x)                             //compare the value to the left because the conditions haven't been met yet
               y--                                               //decrease the counter
         Vals(y + 1) = nextval                                   //store the value in the right position