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 arrowi ← j - 1
array length is not the 'usual' A.length but ratherlength[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.
- for j = 2 to A.length
- key = A[j]
- // Insert A[j] into the sorted sequence A[1 .. j - 1]
- i = j - 1
- while i > 0 and A[i] > key
- A[i + 1] = A[i]
- i = i - 1
- A[i + 1] = key
// Precondition: none