Insertion Sort

A sorting algorithm that inserts each item in the proper place into an initially empty list by comparing it with each item in the list until it finds the new element's successor or the end of the list. A very innefficient sort (on about the same level of efficiency as the bubble sort).

Example Code:

procedure Insertion( var a : anarray; N : integer);

 var i, j, v : integer;

begin
 
 for i := 2 to N do
  begin
    v := a[i]
    j := i;

      {Short circuit evaluation is assumed for
        the AND in the while loop.}
    while (j > 1) AND (a[j-1] > v) do
     begin
      a[j] := a[j-1]
      j := j-1
     end;

    a[j] := v;

  end;

end;

Back to Sorting Algorithms

Example code in C:

/* Insertion sort for integers */

void insertion( int a[], int n ) {
    int i, j, v;
    for(i=1;i<n;i++) {
        v = a[i];
        j = i;
        /* If this element is greater than v,
              move it up one */
        while ( a[j-1] > v ) {
          a[j] = a[j-1]; j = j-1;
	  if ( j <= 0 ) break;
          
        a[j] = v;
        }
    }
}

This code was written by Woi Ang (Who is not tribbel)

While we are at it, here's also an insertion sort example in Java:

  void insertionSort(int a[], int len) {
    int prev = 0;
    for (int i = 1; i < len; i++) {
      int foo = a[i];
      if (a[prev] > foo) {
        do {
          // shift values
          a[prev+1] = a[prev];
          --prev;
        }
        while (prev >= 0 && a[prev] > foo);
        a[++prev] = foo;
      }
      prev = i;
    }
  }

The idea of the insertion sort algorithm is like holding cards in one hand, and for each unsorted card, find where it belongs in the sorted cards, and insert it.

Insertion sort doesn't perform so bad when sorting partially sorted or quasi-sorted lists.  In fact, insertion sort is used in an enhanced version of quick sort, called "quicker sort," also called "enhanced quick sort."  Insertion sort is used in order to reduce stack use caused by recursion, and also to avoid partitioning on short lists, which tend to be less efficient.  Enhanced quick sort also uses tri-median method in order to find a better pivot.

Average running time on a random list is O(n²).

Insertion sort will sort a field of n numbers in the worst case scenario in O(n²) time. In the best case scenario, however, it will sort a field of n numerbers in O(n) time. The best case scenario is when the field is already sorted or almost sorted. This is important to remember and this property of insertion sort makes it a very usefull algorithm for a number of different problems.

A more accurate way to state the effiency of insertion sort is to say that it is both Ω(n) and O(n²).

---

This is an implementation of insertion sort in haskell:

ins x [] = [x]
ins x lst@(y:ys)
  | (x < y)   = x:(lst)
  | otherwise = y:(ins x ys)

isort [] = []
isort (x:xs) = ins x (isort xs)