Insertion Sort (thing)

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²).