Cape Guy

Binary Sorting for ILists

By

I often find myself wanting to deal with sorted lists and, while C# and LINQ make this pretty easy to code, the result using built-in methods is often very inefficient. This is because they run in O(N) time for searching and O(N2) time for sorting as they just use simple loops over the data (what is that big-O notation all about?). LINQ also tends to be pretty allocation heavy (which is bad in Unity right now). What we really need is a simple set of methods which allow the use of binary search and sorting algorithms and perform those sorts in-place, avoiding allocations.

If you’re not sure why this matters, take a look at this sorting algorithm comparison visualisation:

There’s a similar issue with linear vs. binary searches. Though, you can only perform a binary search on sorted data so there can be a tradeoff there for dynamic data sets.

Basically, if you have more than a small amount of data to sort or search, using O(N2) sort algorithms in the wrong place is going to kill your performance. Even an O(N) search run in the wrong place(s) can become a major performance issue.

Now that you’re, hopefully, convinced it’s important… Good news – I’ve written some extensions which use the Quicksort & Binary Search algorithms!

How do I Get Them?

The files you need are here…

And you can also grab the tests if you like (make sure you put them in an editor only folder)

What Do They Do?

  • Add extension methods that let you efficiently sort and search any IList<T> in place, if necessary, and without allocations.
  • For IList<T> – You can use T‘s standard ordering, an IComparer<T> or a lambda sort predicate (Func<T, T, int>).  With the comparer or lambda predicate the return value should behave like the IComparer<T>.Compare method (more info here).
  • The standard ordering and lambda predicate BinarySearch and Sort implementations do not allocate anything. The IComparer<T> implementations make a single allocation to wrap the comparer with a lambda.
  • The following methods have all been implemented for all comparison types:
    • BinaryInsertSorted – Inserts a single member into an already sorted list. Finding the place to insert element can be done in worst case O(logN) however, as the cost of inserting an element into a random position in a list is worst case O(N) this method runs in worst case O(N) time. As such it is not recommended to sort a list using repeated calls to this method – use the Sort method for that purpose. This method is intended for the case where you build a sorted list but only have access to one new value at a time.
    • BinaryLowerBound – Returns the index of the first element in the sorted list which is greater than or equal to the given element. Assumes the list is ordered WRT the sort comparison. Runs in worst case O(logN).
    • BinaryUpperBound – Returns the index of the first element in the sorted list which is greater the given element. Assumes the list is ordered WRT the sort comparison. Runs in worst case O(logN).
    • BinaryFindLast – Returns the index of the last element in the sorted list for which the given predicate is true, -1 if the predicate is never false. Assumes the list is sorted WRT the sort predicate. ie. the predicate has at most one value switch for the list and it is from true to false. Runs in worst case O(logN).
    • BinaryFindFirst – Returns the index of the first element in the sorted list for which the given predicate is true, list.Count if the predicate is never false. Assumes the list is sorted WRT the given predicate. ie. the predicate has at most one value switch for the list and it is from false to true. Runs in worst case O(logN).
    • BinarySearch – Returns the index if a matching element in the list, if such an element exists. Otherwise returns list.Count. Runs in worst case O(logN).
    • IsSorted – Calcules if the list is already sorted WRT the provided sort comparison. Runs in exactly O(N).
    • Sorted – Returns a sorted copy of the list using the Sort method to actually perform the sort.
    • Sort – Sorts the list in place, without allocations. Sorting is performed using Quicksort and so Runs in worst case O(N2) though that is extremely rare and on average it runs in O(NlogN).