Method

Insertion sort is an algorithm to arrange a sequence of elements R1, R2, …, Rn into order. Elements are removed one by one from the unsorted sequence and inserted into the correct position in a new, sorted sequence S.

Sorting is usually implemented in-place. As elements are removed from the end of sequence R, the space freed up is used to extend sequence S. After i insertions, R1, …, Rn-i remain unsorted and the sorted sequence S1, …, Si is stored in elements Rn-i+1, …, Rn.

Pseudo-code

function insertion_sort R
    i ← length R
    while i > 0 do
        j ← i
        temp ← Rj
        while j < length R and Rj+1 < temp do
            Rj ← Rj+1
            j ← j + 1
        Rj ← temp
        i ← i - 1

Example

The example below shows the steps necessary to sort 6 elements. White elements are unsorted, grey elements have been sorted and the red element has been inserted in the current step.

833197153634889381
833197153634889381
833197153634381889
833197153381634889
833197153381634889
833153197381634889
153197381634833889

Analysis

Insertion sort requires n passes to sort a sequence of n elements. With each pass the sorted sequence S increases by one element. On average, Insertion sort will move and compare half of the sorted sequence each pass. The average number of move / compare operations is (n²-n)/4.

The worst case is a sequence sorted in reverse order which requires (n²-n)/2 move / compare operations. Insertion sort runs in Ο(n²) time.

Insertion sort is a stable sorting algorithm. The relative order of equal elements is maintained.

Implementation in Redcode

          org    outer

          temp   equ (outer-1)

outer     nop    }z,             {q
z         mov    #0,             y
q         mov.a  #FIRST+LENGTH-p,p
p         mov    #0,             #0

          mov    {p,             temp
inner     slt    @p,             temp
          jmp    found
          mov    >p,             }p
y         djn    inner,          #0
found     mov    temp,           *p

          djn    outer,          #LENGTH-1

Comparison to other Ο(n²) sort algorithms

Insertion sort is 11 instructions long in Redcode, the same size as Bubble sort. Gnome sort and Selection sort are both shorter, at 9 and 10 respectively.

For the worst case the Redcode Insertion sort requires 1.5n²+5.5n-7 cycles to sort n elements, the same length of time as Selection sort. Bubble sort and Gnome sort are both slower, taking 3n²-3 and 4.5n²-3.5n respectively. The table below shows the number of cycles required to sort n elements:

nInsertion SelectionBubble Gnome
21010911
323232430
439394558
558587295
10198198297415
15413413672960
2070370311971730
5040184018749711075
75884388431687225050
10015543155432999744650
150345683456867497100725
2006109361093119997179300