Data Structures and Algorithms Lecture Notes

13 April 2011 • 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 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 2006 January 24.