# 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 **i**is 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].

- final = [];
- We place
**pivot**value from initial array to**final. final**= [2]; - 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]; - 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]; - Method returns sorted array.

**Input:**

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

**Expected output:**

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

**Ruby code:**