Contents /
Previous /
Next
Sort by repeatedly taking the next item and inserting it into the
final data structure in its proper order with respect to items already
inserted.
Sorting can be done in place by moving the next item past the
end of the sorted items into place by repeatedly swapping it with the
preceding item until it is in place - a linear search and move
combined.
Source Code
Source code
for is the basic insertion sort algorithm:
<![CDATA[
void insertionSort(int numbers[], int array_size)
{
int i, j, index;
for (i=1; i < array_size; i++)
{
index = numbers[i];
j = i;
while ((j > 0) && (numbers[j-1] > index))
{
numbers[j] = numbers[j-1];
j = j - 1;
}
numbers[j] = index;
}
}
]]>
Complexity
Insertion sort has a complexity of O(n2).