{WARNING THIS IS NOT AN EXECUTABLE PROGRAM} {insertion sort -- this is one of the best sorting algorithms for reasonably small arrays } var v: array [0..n] of item; {data to be sorted in a[1],..,a[n] only} begin for k := 1 to n-1 do begin if v[k].key > v[k+1].key {v[k+1] is out of sort} then begin small := v[k+1]; j := k; {move item v[j] down one till right place for v[k+1] is found } repeat v[j+1] := v[j]; j := j-1 until (j = 0) or (v[j].key < small); {note the reason for declaring v[0]} v[j+1] := small end end end.