Insertion sort can be made even more efficient by reducing the number of assignments to one by using a block move instruction, such as the memcpy() POSIX function.
insertion sort(T a[], n)
for i = 1 to n - 1
T x = a[i]
gap = i
while gap > 0 and a[gap - 1] > x
gap--
memcpy(a + gap, a + gap + 1, sizeof(T)*(i - gap))
a[gap] = x
However, block copying data can cause havoc if the data aren’t set up properly; if, for example, the data are C++ class instances containing a smart-pointer instance variable.
This page last modified on 24 January 2006.