AP® Computer Science A glossary
Insertion sort
Course: AP® Computer Science A Shows up in: Unit 4: Data Collections
An iterative sort that inserts each next element into the sorted portion by shifting larger elements right.
Appears in the course and exam description (CED): 4.15.A.14.15.A.3
Insertion sort takes the first element of the unsorted portion, shifts each larger element of the sorted portion one place right, and drops the element into the gap. Its position is correct but not necessarily final, because a smaller element found later can push it right. It is fast on nearly sorted data.
Example
// {29, 12, 41, 7} after each pass:
// pass 1: {12, 29, 41, 7}
// pass 2: {12, 29, 41, 7}
// pass 3: {7, 12, 29, 41}