Insertion Sort Algorithm

According to T. Cormen’s «Introduction to algorithms», it’s ‘efficient algorithm for sorting small number of elements.’. So, after reading this article you will be able to write simple sorting algorithm on your own.

Main principles:

First step — create new array(final), where our final output will be stored. Next, insert our pivot value (first value from initial array) in the final. Then compare each item (i) in initial array (except pivot) with items in final. If iis less than current, insert it before the current item. If not — move to the next item in final. If all values in final are less than i — insert it in the end of an array. After all iterations method should return sorted array(final).

Step-by-step:

Let’s assume, that we our initial array is [2, 3, 1]. Sorted output should look like [1, 2, 3].

1. final = [];
2. We place pivot value from initial array to final. final = [2];
3. We take second value from initial array and compare it with each element in final. 3 > 2. We insert 3 after 2, because it’s higher than all values in final. final = [2, 3];
4. Finally, we take last element from initial array and compare it with items in final. 1 < 2. So, we insert 1 before the 2. final = [1, 2, 3];
5. Method returns sorted array.

Input:
[1, 5, 3, 4, 6, 3]

Expected output:
[1, 3, 3, 4, 5, 6]

Ruby code: