Insertion into a sorted list is part of a collection of standard algorithms.

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:

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

Help & comments

Get help from AP CS Tutor Brandon Horn

Comment on Insertion into a sorted list