List<T> (and SafeList) have a great feature for fast lookups: BinarySearch. However, the list needs to be sorted in order to use it. You could call Sort() first, but that would give back all the performance you got with BinarySearch. It’s better to just keep the list sorted all the time. Unfortunately, there is no function on IList<T>, List<T>, or SafeList to efficiently insert an item into a list that’s already sorted. Today’s article presents an extension function that adds this functionality on to IList<T> and even the non-generic IList so your list will always be sorted for quick lookups with BinarySearch. Read on for the code, unit tests, and a performance test showing the advantages you stand to gain.

First of all, you may be wondering “what about SortedList?” That is indeed a sorted list, but it has several downsides. First, it’s not an IList<T> since it’s really more of a map. Second, because it’s a map it holds key-value pairs mapping the value you want to sort on to the value you actually wanted to store in the list. When they’re the same, you’re just wasting space storing duplicated data. Third, if you want to sort by a custom function you can’t just give a Comparison delegate. Instead, you have to create a class that implements IComparer.

All of that has led me to find a way that works with all IList and IList<T> classes, including List<T>, LinkedList<T>, and SafeList<T>. Extension functions are an easy way to add on the function I wish they came with: InsertIntoSortedList.

InsertIntoSortedList assumes that the list is already sorted, just like BinarySearch. Rather than a linear scan from start to end, it too uses a binary search to find the point at which it should insert the value. At that point it calls Insert rather than doing any explicit indexing. This means it’s SafeList-compatible and allows for each list class to optimize the insertion.

There are actually two overloads of InsertIntoSortedList. The first just takes the value to insert and uses the default comparison for the list’s element type. The second takes a Comparison delegate so you can customize how your list is sorted.

Now let’s take a look at the extension methods:

using System;
using System.Collections;
using System.Collections.Generic;
 
/// <summary>
/// Container for extension functions for the System.Collections.Generic.IList{T} and System.Collections.IList
/// interfaces that inserts elements lists that are presumed to be already sorted such that sort ordering is preserved
/// </summary>
/// <author>Jackson Dunstan, http://JacksonDunstan.com/articles/3189</author>
/// <license>MIT</license>
public static class IListInsertIntoSortedListExtensions
{
	/// <summary>
	/// Insert a value into an IList{T} that is presumed to be already sorted such that sort
	/// ordering is preserved
	/// </summary>
	/// <param name="list">List to insert into</param>
	/// <param name="value">Value to insert</param>
	/// <typeparam name="T">Type of element to insert and type of elements in the list</typeparam>
	public static void InsertIntoSortedList<T>(this IList<T> list, T value)
		where T : IComparable<T>
	{
		InsertIntoSortedList(list, value, (a,b) => a.CompareTo(b));
	}
 
	/// <summary>
	/// Insert a value into an IList{T} that is presumed to be already sorted such that sort
	/// ordering is preserved
	/// </summary>
	/// <param name="list">List to insert into</param>
	/// <param name="value">Value to insert</param>
	/// <param name="comparison">Comparison to determine sort order with</param>
	/// <typeparam name="T">Type of element to insert and type of elements in the list</typeparam>
	public static void InsertIntoSortedList<T>(
		this IList<T> list,
		T value,
		Comparison<T> comparison
	)
	{
		var startIndex = 0;
		var endIndex = list.Count;
		while (endIndex > startIndex)
		{
			var windowSize = endIndex - startIndex;
			var middleIndex = startIndex + (windowSize / 2);
			var middleValue = list[middleIndex];
			var compareToResult = comparison(middleValue, value);
			if (compareToResult == 0)
			{
				list.Insert(middleIndex, value);
				return;
			}
			else if (compareToResult < 0)
			{
				startIndex = middleIndex + 1;
			}
			else
			{
				endIndex = middleIndex;
			}
		}
		list.Insert(startIndex, value);
	}
 
	/// <summary>
	/// Insert a value into an IList that is presumed to be already sorted such that sort ordering is preserved
	/// </summary>
	/// <param name="list">List to insert into</param>
	/// <param name="value">Value to insert</param>
	public static void InsertIntoSortedList(this IList list, IComparable value)
	{
		InsertIntoSortedList(list, value, (a,b) => a.CompareTo(b));
	}
 
	/// <summary>
	/// Insert a value into an IList that is presumed to be already sorted such that sort ordering is preserved
	/// </summary>
	/// <param name="list">List to insert into</param>
	/// <param name="value">Value to insert</param>
	/// <param name="comparison">Comparison to determine sort order with</param>
	public static void InsertIntoSortedList(
		this IList list,
		IComparable value,
		Comparison<IComparable> comparison
	)
	{
		var startIndex = 0;
		var endIndex = list.Count;
		while (endIndex > startIndex)
		{
			var windowSize = endIndex - startIndex;
			var middleIndex = startIndex + (windowSize / 2);
			var middleValue = (IComparable)list[middleIndex];
			var compareToResult = comparison(middleValue, value);
			if (compareToResult == 0)
			{
				list.Insert(middleIndex, value);
				return;
			}
			else if (compareToResult < 0)
			{
				startIndex = middleIndex + 1;
			}
			else
			{
				endIndex = middleIndex;
			}
		}
		list.Insert(startIndex, value);
	}
}

And here are the unit tests making sure that these extension methods work. To run them in Unity, get the Unity Test Tools. To run them outside of Unity, just add them to any NUnit test runner.

using System.Collections;
using System.Collections.Generic;
 
using NUnit.Framework;
 
[TestFixture]
public class TestIListTInsertIntoSortedListExtensions
{
	[TestCase('b', new []{ 'b', 'c', 'd', 'h', 'i' }, Description = "Contiguous Beginning")]
	[TestCase('a', new []{ 'a', 'c', 'd', 'h', 'i' }, Description = "Before Contiguous Beginning")]
	[TestCase('j', new []{ 'c', 'd', 'h', 'i', 'j' }, Description = "Contiguous End")]
	[TestCase('k', new []{ 'c', 'd', 'h', 'i', 'k' }, Description = "Past Contiguous End")]
	[TestCase('d', new []{ 'c', 'd', 'd', 'h', 'i' }, Description = "Existing element in middle")]
	[TestCase('e', new []{ 'c', 'd', 'e', 'h', 'i' }, Description = "New element in middle")]
	[TestCase('f', new []{ 'c', 'd', 'f', 'h', 'i' }, Description = "New element in middle")]
	[TestCase('g', new []{ 'c', 'd', 'g', 'h', 'i' }, Description = "New element in middle")]
	public void RespectsIComparableOrder(char value, char[] expected)
	{
		var list = new List<char>() { 'c', 'd', 'h', 'i' };
		list.InsertIntoSortedList(value);
		CollectionAssert.AreEqual(expected, list);
	}
 
	[Test]
	public void RespectsComparisonOrder()
	{
		var list = new List<int>() { 10, 12, 11, 13 };
		list.InsertIntoSortedList(14, SortEvenBeforeOddThenAscending);
		CollectionAssert.AreEqual(new [] { 10, 12, 14, 11, 13 }, list);
	}
 
	private int SortEvenBeforeOddThenAscending(int a, int b)
	{
		var aEven = (a & 1) == 0;
		var bEven = (b & 1) == 0;
		if (aEven == true && bEven == false)
		{
			return -1;
		}
		if (bEven == true && aEven == false)
		{
			return 1;
		}
		return a - b;
	}
}
 
[TestFixture]
public class TestIListInsertIntoSortedListExtensions
{
	[TestCase('b', new []{ 'b', 'c', 'd', 'h', 'i' }, Description = "Contiguous Beginning")]
	[TestCase('a', new []{ 'a', 'c', 'd', 'h', 'i' }, Description = "Before Contiguous Beginning")]
	[TestCase('j', new []{ 'c', 'd', 'h', 'i', 'j' }, Description = "Contiguous End")]
	[TestCase('k', new []{ 'c', 'd', 'h', 'i', 'k' }, Description = "Past Contiguous End")]
	[TestCase('d', new []{ 'c', 'd', 'd', 'h', 'i' }, Description = "Existing element in middle")]
	[TestCase('e', new []{ 'c', 'd', 'e', 'h', 'i' }, Description = "New element in middle")]
	[TestCase('f', new []{ 'c', 'd', 'f', 'h', 'i' }, Description = "New element in middle")]
	[TestCase('g', new []{ 'c', 'd', 'g', 'h', 'i' }, Description = "New element in middle")]
	public void RespectsIComparableOrder(char value, char[] expected)
	{
		var list = new ArrayList() { 'c', 'd', 'h', 'i' };
		list.InsertIntoSortedList(value);
		CollectionAssert.AreEqual(expected, list);
	}
 
	[Test]
	public void RespectsComparisonOrder()
	{
		var list = new ArrayList() { 10, 12, 11, 13 };
		list.InsertIntoSortedList(14, SortEvenBeforeOddThenAscending);
		CollectionAssert.AreEqual(new [] { 10, 12, 14, 11, 13 }, list);
	}
 
	private int SortEvenBeforeOddThenAscending(object a, object b)
	{
		var aInt = (int)a;
		var bInt = (int)b;
		var aEven = (aInt & 1) == 0;
		var bEven = (bInt & 1) == 0;
		if (aEven == true && bEven == false)
		{
			return -1;
		}
		if (bEven == true && aEven == false)
		{
			return 1;
		}
		return aInt - bInt;
	}
}

Finally, let’s run a quick performance test to see how long it takes to insert a bunch of items and then find them all. The first approach simply uses Add and IndexOf. The second uses InsertIntoSortedList and BinarySearch.

using System.Collections.Generic;
 
using UnityEngine;
 
public class TestScript : MonoBehaviour
{
	private const int ListSize = 100000;
 
	private string report = string.Empty;
 
	private int[] values;
 
	void Start()
	{
		values = new int[ListSize];
		var random = new System.Random();
		for (var i = 0; i < ListSize; ++i)
		{
			values[i] = random.Next(int.MinValue, int.MaxValue);
		}
		report = "List,Insert Time,Search Time\n"
			+ "Unsorted," + TestUnsorted() + "\n"
			+ "Sorted," + TestSorted();
	}
 
	string TestUnsorted()
	{
		var list = new List<int>(ListSize);
		var stopwatch = new System.Diagnostics.Stopwatch();
		stopwatch.Start();
		for (var i = 0; i < ListSize; ++i)
		{
			list.Add(values[i]);
		}
		var insertTime = stopwatch.ElapsedMilliseconds;
		stopwatch.Reset();
		stopwatch.Start();
		for (var i = 0; i < ListSize; ++i)
		{
			list.IndexOf(values[i]);
		}
		var searchTime = stopwatch.ElapsedMilliseconds;
		return insertTime + "," + searchTime;
	}
 
	string TestSorted()
	{
		var list = new List<int>(ListSize);
		var stopwatch = new System.Diagnostics.Stopwatch();
		stopwatch.Start();
		for (var i = 0; i < ListSize; ++i)
		{
			list.InsertIntoSortedList(values[i]);
		}
		var insertTime = stopwatch.ElapsedMilliseconds;
		stopwatch.Reset();
		stopwatch.Start();
		for (var i = 0; i < ListSize; ++i)
		{
			list.BinarySearch(values[i]);
		}
		var searchTime = stopwatch.ElapsedMilliseconds;
		return insertTime + "," + searchTime;
	}
 
	void OnGUI()
	{
		GUI.TextArea(new Rect(0, 0, Screen.width, Screen.height), report);
	}
}

If you want to try out the test yourself, simply paste the above code into a TestScript.cs file in your Unity project’s Assets directory and attach it to the main camera game object in a new, empty project. Then build in non-development mode for 64-bit processors and run it windowed at 640×480 with fastest graphics. I ran it that way on this machine:

  • 2.3 Ghz Intel Core i7-3615QM
  • Mac OS X 10.10.5
  • Unity 5.1.2f1, Mac OS X Standalone, x86_64, non-development
  • 640×480, Fastest, Windowed

And here are the results I got:

List Insert Time Search Time
Unsorted 0 22566
Sorted 403 19

Insert Time

Search Time

Inserting into the unsorted list is blazingly fast as the capacity for all the items has already been allocated. It’s simply assigning to an array index. On the other hand, InsertIntoSortedList has to find the correct insertion point first. That’s an O(log(N)) binary search with an O(N) insertion, which does take quite a while longer (403 milliseconds) than simply assigning to the end of an array (0 milliseconds).

Searching is where the tables turn. The unsorted list needs to be linearly scanned from start to end to find the desired element. That’s an O(N) operation. The sorted list uses BinarySearch to do an O(log(N)) lookup and the results really show. Searching the sorted list takes 19 milliseconds but searching the unsorted list takes a whopping 22566 milliseconds!

So what we have is a classic tradeoff. Which do you want to take longer, inserting or searching? The answer depends on several factors, such as how often you intend to insert, how often you intend to search, how long your list is, and if you get any other benefits from having a sorted list beyond just fast searching.

This means that the InsertIntoSortedList extension function is just another tool in your toolbox. It’s not right for all cases since it’s demonstrably slower at inserting, but it just may come in handy the next time you need to keep an IList sorted.

Spot a bug? Have a question or suggestion? Post a comment!