Preliminaries...

Insertion sort shows up several times in chapter 2 of CLRS.

In 3rd edition,

on p.18 where discussion is invariants and
on p.26 where running time is carefully considereded. (See A.1)

In 2nd edition, p.17 & p.24, respectively.

Please note in 2nd edition

comments delimiter is a little triangle
▹ Insert A[j] into the sorted sequence A[1 .. j - 1]

assignment operator is a left arrow
i ← j - 1

array length is not the 'usual' A.length but rather
length[A]

 


In the below, it is understood from context that A is a sequence of values stored in an array and by CLRS convention the indexing begins at 1.

    // Precondition:     none

    InsertionSort(A)

  1. for j = 2 to A.length
  2. key = A[j]
  3. // Insert A[j] into the sorted sequence A[1 .. j - 1]
  4. i = j - 1
  5. while i > 0 and A[i] > key
  6. A[i + 1] = A[i]
  7. i = i - 1
  8. A[i + 1] = key