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:

• 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

Help & comments

Get help from AP CS Tutor Brandon Horn

Comment on Insertion into a sorted list