Insertion into a sorted list is a standard algorithm. A `while`

loop is used to find the position at which the element should be inserted, but not to insert the element. The element is inserted, using the `add`

method, after the `while`

loop.

## Insertion of a `String`

into a sorted list

```
public static void insert(ArrayList<String> sortedList, String toInsert)
{
int i = 0;
while(i < sortedList.size() && toInsert.compareTo(sortedList.get(i)) > 0)
i++;
sortedList.add(i, toInsert);
}
```

In the method above, `sortedList`

is a list that is already sorted in ascending (increasing/non-decreasing/smallest to largest) order. The method inserts `toInsert`

into `sortedList`

such that sortedList remains sorted.

The method uses a standard algorithm for insertion into a sorted list. The loop runs while `i`

is valid in `sortedList`

and while `toInsert`

is greater than the element at index `i`

.

This approach works without special cases. It neatly handles:

- insertion into an empty list. The loop will not run.
`i`

will remain`0`

. - insertion at the beginning of a non-empty list. The loop will not run.
`i`

will remain`0`

. - insertion anywhere in the middle of a non-empty list. The loop will end when
`toInsert`

is less than or equal to the value at`i`

. - insertion at the end of a non-empty list. The loop will end when
`i == sortedList.size()`

.

It is possible to perform the insertion with a for loop; however, several of the cases above become special cases. It is also easy to accidentally insert the element more than once.

Practice standard algorithms with AP CS Tutor Brandon Horn.

## Selected AP CS A FR that request insertion into a sorted list

- 2012 A FR #1 ClimbingClub: 2012 FR PDF / ClimbingClub solution