# Algorithms – Sorting – Insertion Sort

Insertion sort is considered as one of simplest of all the sorting algorithms. The strategy behind insertion sort is to pick up an element from the list and place it at the right position in the list at the end of each iteration.

Algorithm:

//Input: An array of elements to be sorted denoted by ‘A’ and the size of the array denoted by ‘n’

//Output: In-place sorted array

//Requirement: The contents of the array to be sorted should be comparable with each other i.e. it is expected that relational operations can be applied on the contents of the array.

procedure insertionSort (A, n)
for i = 1 to n-1 do
input (A, i, A[i])
done
end

procedure insert (A, pos, value)
i = pos-1
while (i>=0 && A[i]>value) do
if (A[i]>A[i+1]) then
swap A[i] and A[i+1]
i=i-1
endif
done
swap A[i+1] and value
end

Source Code snippet for the above Algorithm in C++:

```/* Few assumptions:
* There exists a class named Sort that contains utility methods along
* with sorting methods. The utility methods take care of reading the
* input into an array named 'input' and a variable titled
* 'elementCount' represents the total number of elements in an array.
*/

template<typename elementType>
void Sort<elementType>::insertionSort() {
for (int i = 1; i <= elementCount - 1; i++) {
// For all elements starting from position 1 not 0.
insert(input, i, input[i]);
}
}

// Insertion Sort helper function
template<typename elementType>
void Sort<elementType>::insert(elementType input[], int pos, elementType value) {
int i = pos - 1;
// Shift all the element that are greater than the current element under
// consideration to the right by 1 position.
while (i >= 0 && *(input + i) > value) {
*(input + i + 1) = *(input + i);
i -= 1;
}
// Insert the current element at the right position.
*(input + i + 1) = value;
}
```

Reference:

• Book: Introduction to the Design and Analysis of Algorithms by Anany Levitin. Copyright 2003, 0-201-74395-7.
• Book: Algorithms in a Nutshell by George T. Heineman, Gary Pollice, and Stanley Selkow. Copyright 2009 George Heineman, Gary Pollice, and Stanley Selkow, 978-0-596-51624-6.
• Wikipedia: http://en.wikipedia.org/wiki/Insertion_sort