Putting It Together: Insertion Sort

Part of: ArrayList

A Capstone Algorithm This lesson combines everything: get, set, size, indexed loops, and in-place modification. Insertion sort is a standard sorting algorithm that the AP exam expects you to read and trace, and it maps cleanly onto an ArrayList. The Idea Insertion sort builds a sorted region at the front of the list. For each new element, it slides it leftward past any larger elements until it lands in the correct spot, like sorting playing cards in your hand: - Treat index 0 as a sorted region of size one. - Take the element at index i and call it the key . - Shift every element in the sorted region that is larger than the key one slot right. - Drop the key into the opened gap. Implementation Trace it on [3, 1, 2]: - i=1, key=1: shift 3 right - [3, 3, 2], place 1 - [1, 3, 2]. - i=2, key=2: shift 3 right - [1, 3, 3], place 2 - [1, 2, 3]. Sorted. Why It Matters Insertion sort is O(n^2) in the worst case but efficient for small or nearly sorted lists. More importantly, it exercises the full ArrayList toolkit: index management, get/set, and a careful inner loop. If you can write and trace this, you understand ArrayList deeply. Summary - Insertion sort grows a sorted prefix one element

Challenge: Insertion Sort