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.
How do I Get Them?
The files you need are here…
- IListExtensions.cs – A small collection of basic extensions to IList
- IListSortExtensions.cs – All the sorting magic
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.
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
Sortimplementations 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
Sortmethod 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,
-1if 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.Countif 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
Sortmethod 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).