The Problem 

Recently I ran into a need to keep a list of integers sorted in ascending order. The list was used as an internal representation of a set, so I didn't have to create a new class implementing IList<T> or anything similar. The whole issue was to implement adding new elements properly. Of course, I started with writing a routine to find a proper place for a new element, move all subsequent elements and so on. This is quite a bit of code and it is easy to make a mistake here.

The scaffolding looks like this:

public class Set
{
    List<int> sortedList = new List<int>();
    public void Add(int i)
    {
        // To implement.
    }
}

The Solution 

There is, however, a very simple way to do add elements in such a way that the whole list stays sorted. How do you find a proper place for a new element if you have a sorted list? You use binary search. As it turned out, List<T>.BinarySearch method returns very useful return value. If the element I am looking for is already in the list, it returns its index. This way I know if I should add the element to the list or not (I don't want duplicate elements so I don't do anything if this happens). If the element is not in the list, List<T>.BinarySearch method returns a negative number that is a binary complement of an index of the first element that is greater that the element I passed to binary search method. If there is no greater element in the list, a binary complement of the value of Count property is returned.

How can that be useful? If we take a binary complement of the value returned by List<T>.BinarySearch (if it is lower than 0, of course), we have an index that we should use to insert our element in order to keep the list sorted! If the binary complement we get is equal to Count, the element is appended at the end of the list, as expected. Here is how the simple implementation might look like:

public void Add(int i)
{
    int index = sortedList.BinarySearch(i);
    if (index < 0)
    {
        sortedList.Insert(~index, i);
    }
}

Little Optimization

There is a little optimization that I wanted to implement. The typical scenario for my set class is to initialize it by adding multiple elements in ascending order. With the current implementation, there would be many binary searches that would always end up returning the binary complement of the Count value. We can circumvent this easily by checking if the added element is greater than the last element and directly appending it at the end of the list, if this is the case. Here is how the final implementation could look like:

public void Add(int i)
{
    if (sortedList.Count == 0)
    {
        sortedList.Add(i);
        return;
    }
    if (sortedList[sortedList.Count - 1] < i)
    {
        sortedList.Add(i);
        return;
    }
    int index = sortedList.BinarySearch(i);
    if (index < 0)
    {
        sortedList.Insert(~index, i);
    }
}