Insertion Sorting

Insertion sorting is an O(N2) algorithm for sorting a list of N items using comparisons. The idea is to divide the data (a sequence of items) into two sections: one sorted (initially empty) and one unprocessed (initially containing the entire input sequence). Each unprocessed item in turn is then inserted at the approriate point in the sorted list. In the worst case, each of the N elements requires an average of N operations either to find the desired insertion point (for sequences represented with linked structures) or to perform the actual insertion (for sequences represented with arrays).

The particular variant represented in this demonstration uses an array for the sequence and combines the operations of searching for an insertion point and moving array elements over to make room. Items displayed in pink are unprocessed and items displayed in green have been moved as needed to accommodate the element currently being inserted. The program moves elements by swapping with their predecessors; while this causes more stores than necessary, it slightly clarifies the comparisons being performed and, since swaps do not change the set of array values, makes it clear that the result must be a permutation of the input, as required.

The "inversion count" is a measure of "unsortedness". It is the number of pairs of items in the array that are out of order—in which the first (lower-indexed) item is greater than the second. Insertion sorting has the property that the total time required to sort an N-element sequence is proportional to N plus the number of inversions (why?). Thus, nearly sorted inputs can be sorted in nearly linear time.

Fast Slow
Input size:
Initial array: Array: Inversion count: # comparisons: