Insertion Sort

• is a most natural and general one
• Insertion Sort orders a list in the same way we would order a hand of playing cards.
• its worst case and average behavior analysis are easy.
• Using Insertion Sort, the number of comparisons on a list of size n varies, because, if the numbers are already in order, further comparisons are avoided. So we will find the average number of comparisons.
• Using limits and probability, we find that the average number of comparisons is (n-1)(n/4) + k, where k increases for larger values of n.

Pros: Relatively simple and easy to implement.
Cons: Inefficient for large lists.

The insertion sort works just like its name suggests - it inserts each item into its proper place in the final list. The simplest implementation of this requires two list structures - the source list and the list into which sorted items are inserted. To save memory, most implementations use an in-place sort that works by moving the current item past the already sorted items and repeatedly swapping it with the preceding item until it is in place.

Like the bubble sort, the insertion sort has a complexity of O(n²). Although it has the same complexity, the insertion sort is a little over twice as efficient as the bubble sort.

Steps in Insertion Sort:
1. Compare the first two numbers, placing the smallest one in the first position.
2. Compare the third number to the second number. If the third number is larger, then the first three numbers are in order. If not, then swap them.
3. Now compare the numbers in positions one and two and swap them if necessary.
4. Proceed in this manner until reaching the end of the list.

Example:

Empirical Analysis

Insertion Sort Efficiency

The graph demonstrates the n² complexity of the insertion sort.

The insertion sort is a good middle-of-the-road choice for sorting lists of a few thousand items or less. The algorithm is significantly simpler than the shell sort, with only a small trade-off in efficiency. At the same time, the insertion sort is over twice as fast as the bubble sort and almost 40% faster than the selection sort. The insertion sort shouldn't be used for sorting lists larger than a couple thousand items or repetitive sorting of lists larger than a couple hundred items.

Source Code

Below is the basic insertion sort algorithm.

void insertionSort(int numbers[], int array_size)

{

int i, j, index;

for (i=1; i < style="">

{

index = numbers[i];

j = i;

while ((j > 0) && (numbers[j-1] > index))

{

numbers[j] = numbers[j-1];

j = j - 1;

}

numbers[j] = index;

}

}