Lecture Notes for Advanced Programming I

31 January 2006 • Sorting Basics

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 class instances can cause havoc if the class isn't set up properly; if, for example, a class instance contains a smart-pointer instance variable.

This page last modified on 24 January 2006.