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

^{2}).