Insertion Sort Simplified


Desktop-as-a-Service Designed for Any Cloud ? Nutanix Frame

Click here for a larger image.

Environment: This code might be specific to some environments, but the concept of the sorting remains the same.

Fundamental Concept

Approximately ten kinds of sorting methods are available, namely Heap, Quick, Merge, Insertion, Shell, Selection, Bubble, Linear, Address Selection, and Radix sort. Recently, when I was trying to go through the coding of an Insertion sort, I searched the Internet for the same and fortunately found some resources (U.S. universities), where the desired code was explained. I found the code a bit cumbersome to keep track of and difficult to understand (also debug), so I prepared myself for writing my own.

Prior to explaining the code, I will discuss the technique that is being applied to sort an array by using the Insertion sort method. As the name implies, the Insertion sort works on the insertion rule. In simpler terms: a number (at a current position in the array) is being compared with each of the array elements, from the begining of the list (array) until the current position. If the number is found to be less than the one already present, the element is transferred from its original position to this (new) position. That's all, folks.

To fully understand the concept, I have created an example. Let us assume that we have an array of 10 numbers (all positive integers); in other words, 10, 9, 1, 8, 3, 7, 4, 6, 5, and 2. According to the condition explained earlier, the number 9 should be compared with 10. Because the number 9 is less than 10, we will perform a transfer operation for 9. Here comes an important step. Placing a number at the begining of the list (or somewhere else) will cause all the elements (right from the newly found location) to shift one position right. Hence, special care has been taken in the coding to perform the desired job. When we are to make a transfer, first we store the element at its current position in a temporary variable, so that when the entire list is shuffuled the element is not lost. This methodology is followed during the entire sort operation.

Thus, we see that, after the first step, our intermediatary output becomes 9, 10, 1, 8, 3, 7, 4, 6, 5, and 2. Similarly, we can trace out the entire sequence as follows:

After Iteration 1 -  9, 10,  1,  8,  3,  7,  4,  6,  5,  2
After Iteration 2 -  1,  9, 10,  8,  3,  7,  4,  6,  5,  2
After Iteration 3 -  1,  8,  9, 10,  3,  7,  4,  6,  5,  2
After Iteration 4 -  1,  3,  8,  9, 10,  7,  4,  6,  5,  2
After Iteration 5 -  1,  3,  7,  8,  9, 10,  4,  6,  5,  2
After Iteration 6 -  1,  3,  4,  7,  8,  9, 10,  6,  5,  2
After Iteration 7 -  1,  3,  4,  6,  7,  8,  9, 10,  5,  2
After Iteration 8 -  1,  3,  4,  5,  6,  7,  8,  9, 10,  2
After Iteration 9 -  1,  2,  3,  4,  5,  6,  7,  8,  9, 10

In the preceding sequence of operations, numbers shown with bold and underlined formatting indicates the element transferred in that iteration. A point to be noticed here is that we require 9 iterations (in total) to sort an array of 10 elements. Thus, we can generalize this result as: We require (N-1) iterations to sort an array of N elements. The time complexity of this sorting method is the order of N2; in other words, O(N2). Though I am very well aware of the time-complexity factor, I don't know, for the Insertion sort, how it comes to be N2. Well, this was all about the Insertion sort method. This sorting method is not the most efficient and you must use Heap, Quick, or Merge sort, the time complexity (for the average and best case) of which are NLog2N. Below, you will find the code written in C. In the coding (though it is self explainatory), the k variable denotes the position found for the current element in the array.

Source Code

#include <stdio.h>
#include <conio.h>
#define MAX 20

static int arr[MAX];
int n, temp, pos;
int i, j, k;

printf("Enter the number of elements : ");
scanf("%d", &n);

printf("Enter the elements now :\n");
for (i = 0; i < n; i++)
    scanf("%d", &arr[i]);

i = 0;
pos = 0;
for (i = 0; i < n; i = (pos + 1))
    j = pos + 1;
    /* find out the jth element's appropriate position */
    for (k = 0; arr[j] > arr[k] && (k < j); k++);
    /* shift the list elements if the element's position is 
     * found */
    if (k < j)
        temp = arr[j];
        pos = j;
        printf("\nk = %d", k);
        for (; j >= k; j--)
            arr[j] = arr[j - 1];
        arr[k] = temp;
        printf("\tIntermediate o/p is : ");
        for (i = 0; i < n; i++)
            printf("%2d ", arr[i]);

printf("\n\nInsertion sorted list is : \n");
for (i = 0; i < n; i++)
    printf("%d ", arr[i]);



Download demo project - 5 Kb
Download source - 568 Bytes


  • Who would use Insertion Sort?

    Posted by Legacy on 02/22/2004 08:00am

    Originally posted by: Jeffrey Walton

    Take a look at bucket sort:

    Bucket Sort uses insertion sort...yeah

    • Insertion Sort works pretty well

      Posted by Ecuador -=[NM]=- on 05/01/2004 02:08pm

      Before I ever read this article, I wrote a sort engine based on this technique, and compared to other sort engines ( bubble sort, quick sort ) I yielded quite good ( and first of all pretty fast ) results. I will post my engine ( written on Power++ (Optima) ) if anyone is interested. Unfortunately I am on vacation while I write this, so please be patient :) Greets Ecuador

  • Insertion sorting

    Posted by Legacy on 02/06/2003 08:00am

    Originally posted by: Luca Piccarreta

    The complexity of the algorithm is O(N^2)
    because for every insertion you averagely make
    N comparisons (well, I'd guess N/4) and N exhanges.
    Much of the code on the internet is cumbersome,
    but please do not ever put this kind of code in
    your software! :)
    Use STL
    which, you said that, is QuickSort and *is* faster.
    Every sorting algorithm has its advantages, like
    locality, number of comparisons, number of exchanges...
    but Insert Sort has none, as far as I know.

  • Let me clarify first.

    Posted by Legacy on 02/06/2003 08:00am

    Originally posted by: Krishna

    Dear Luca and Peter,
    Thank you very much for posting your valuable comments. I must clarify you the same that my sole purpose of writing this article was to introduce the visitors, the concept of Insertion Sort. I kept the article as simple as possible. I myself know that the other sorting algorithms are much more efficient than the one I have shown in my article, but again I have mentioned that this (Insertion Sort) is not the most efficient algorithm.

    Besides this, if you really did not like the article, simply switch over to another page. ;)

    Krishna Kumar Khatri
    Jaipur, India.

  • A note to Peter

    Posted by Legacy on 02/06/2003 08:00am

    Originally posted by: Anand Balaji

    Ya Peter,
    why don't you demonstrate your programming skills? What are you currently coding... DOOM 4? LOL

  • stupid article

    Posted by Legacy on 02/05/2003 08:00am

    Originally posted by: Peter

    This is the most utterly useless, totally ridiculous article
    written by some ignorant person...The article has no depth.

    If you are stupid, you dont need to let the entire world know about it...

  • You must have javascript enabled in order to post comments.

Leave a Comment
  • Your email address will not be published. All fields are required.

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date