Ordered Insertion

Ordered insertion places a new element into an already-sorted ArrayList at exactly the position that preserves the sort order. The list is never fully re-sorted — only the new element finds its home.

This is the same logic that powers insertion sort, but applied to a single new value at a time. Done repeatedly, it maintains a sorted list throughout the program's life.

On the AP exam, ordered insertion appears in FRQs that describe leaderboards, ranked queues, or any "keep in order" workflow.

The template (ascending order)

public void insertSorted(ArrayList<Integer> list, int value) {
    for (int i = 0; i < list.size(); i++) {
        if (value < list.get(i)) {
            list.add(i, value);
            return;
        }
    }
    list.add(value);   // larger than every element — append
}

The loop scans for the first index whose element is larger than value. Inserting there shifts that element (and the rest) right, placing value exactly where it belongs.

If the loop completes without finding a larger element, value is the new maximum — append with add(value).

For sorting objects

When the list holds objects, use an accessor and the appropriate comparison:

public void insertStudentByGpa(ArrayList<Student> list, Student newStudent) {
    for (int i = 0; i < list.size(); i++) {
        if (newStudent.getGpa() < list.get(i).getGpa()) {
            list.add(i, newStudent);
            return;
        }
    }
    list.add(newStudent);
}

Strict vs non-strict comparison

• < places equal-value elements after existing ones (stable in arrival order).
• <= places them before existing equal elements.

The AP exam usually accepts either, but be consistent with the prompt's intent.

Edge cases

• Empty list: loop doesn't run; add(value) at the end places the only element.
• Smaller than every element: first iteration finds list.get(0) larger; insert at index 0.
• Larger than every element: loop completes; append handles it.