IList Sorting Performance Benchmarks¶

Unity Helpers ships several custom sorting algorithms for IList<T> that cover different trade-offs between adaptability, allocation patterns, and stability. This page gathers context and benchmark snapshots so you can choose the right algorithm for your workload and compare results across operating systems.

Algorithm Cheatsheet¶

What does “stable” mean? Stable sorting algorithms preserve the relative order of elements that compare as equal. This matters when items carry secondary keys (e.g., sorting people by last name but keeping first-name order deterministic). Unstable algorithms can reshuffle equal entries, which is usually fine for numeric keys but can break deterministic pipelines.

The Stable? column is a promise the test suite holds. IListSortCorrectnessTests decorates every element with its original index and enumerates a bounded but genuinely exhaustive domain -- every sequence over a three symbol alphabet up to length six, every binary sequence up to length ten, and every permutation of seven distinct elements -- checking that each result is a permutation of its input rather than merely sorted, and that every algorithm the table calls stable kept equal elements in order. A new SortAlgorithm member fails the suite until the table is extended.

Heads up: Ghost Sort and Meteor Sort have no reachable upstream. Both were published by Will Stafford Parsons and both repositories now return 404, so the implementation in this package is the reference for what these algorithms do here. Anything a third party reports about them cannot be checked against a source.

JesseSort¶

JesseSort adapts Jesse Lew's dual-patience design. It handles sorted, reverse-sorted, and equal input in linear time. Pile assignments are recorded, reconstructed into contiguous ascending piles, then merged bottom-up, one adjacent pair at a time: an ordered-boundary shortcut emits a single copy when two neighboring piles already read as one sorted run, and a reverse-disjoint shortcut block-swaps the pair when every element of the right pile precedes every element of the left one. Upstream alignment is still in progress; the pairwise-merge adaptation's current measurements are available in the tracking issue. The historical Jesse columns below measure the previous C# port, and the tracking issue also holds the superseded numbers for the intermediate k-way merge adaptation.

Where the Time Actually Goes¶

Every algorithm here sorts a T[], never an IList<T> directly. Reaching an element through the IList<T> indexer is an interface call, and a sort makes O(n log n) of them; copying a list into a pooled array and copying it back is 2n moves and then the whole sort runs on direct array indexing. Pass a T[] and it is sorted in place with no copy at all.

Measured on .NET 9 with a struct comparer, sorting int, best of nine runs, the same source before and after the change:

The one shape that pays rather than gains is a List<T> an adaptive sort would finish in O(n) anyway: there the copy is most of the work, and it costs tens of microseconds on 100,000 elements. These are desktop CLR numbers, where the JIT can speculatively devirtualize List<T>; a Unity player cannot, so the run the Unity benchmark below produces is the one that describes a build.

Why a List<T> is copied rather than sorted where it lies¶

Copying looks like the wasteful option and is not. Sorting a List<T> in place was measured against copying it, using a struct accessor so the in-place path paid no interface dispatch at all, the best case an in-place sort can have:

A sort makes O(n log n) element accesses and a copy is O(n) contiguous bytes, so paying a slightly dearer access n log n times to save 2n copies loses at every size and shape measured. The right-hand columns are the same to within noise, which is the point: the copy costs nothing measurable, and the array accesses inside the sort are what the whole exercise is buying.

Both directions of that copy are bulk operations. CopyTo is on ICollection<T>, so reading is one Array.Copy for any list that implements it sensibly. Writing back is one Array.Copy for a List<T> (AddRange takes its ICollection<T> fast path for an ArraySegment<T>), which is 4.4x to 13x faster than assigning through the indexer:

So: a T[] is sorted where it lies, a List<T> moves in and out in two bulk copies, and any other IList<T> reads in bulk and writes back through its indexer, because that is all the interface offers.

Bulk Operations on a List¶

Sorting is not the only IList<T> operation that was reaching every element through an interface call. The same measurement was repeated for the rest of them, and it splits cleanly in two.

An operation that always touches the whole range can afford a copy, and often does not need one, because the BCL already has a bulk primitive for it. Reverse and Fill take Array.Reverse and Array.Fill; List<T> carries its own Reverse(index, count). Shift stopped reversing anything: a rotation is two contiguous runs of the input, so the copy is written back in two Array.Copy calls rather than three reversal passes.

An operation that can stop early must never copy. IndexOf and LastIndexOf with a predicate return at the first match, and a copy would have read every remaining element before the predicate ran once. They get the free half of the change (direct indexing when the list already is a T[]) and nothing else.

Measured on .NET 9, int elements, best of nine runs, the same sources before and after. The IList<T> column is a list that is neither a T[] nor a List<T>, measured against two implementations so the JIT cannot prove the receiver's type and devirtualize the indexer; a first pass that used one sealed class reported a 4x regression that did not exist:

Reverse on an IList<T> is unchanged by design: a partial range has no bulk write-back, and copying the whole list to reverse a few elements of it would be a pessimization.

Some of the IList<T> column is not the copy at all. Count was being read on every iteration of every loop (one interface call per element, for a value that cannot change) and hoisting it alone is worth 1.26x to 1.76x. That accounts for the whole of Fill(value)'s gain there, which is why it copies only for a list that offers bulk replacement and runs a plain hoisted loop for anything else.

A value that cannot change, except where it can. The methods that take a Func<> (Fill(factory), IndexOf, LastIndexOf, FindAll, Partition) deliberately keep re-reading Count and give up that 1.26x to 1.76x. A caller's factory or predicate can remove elements from the list it is being run over, and a hoisted bound then indexes past the end of a shorter list: an ArgumentOutOfRangeException out of a public API, where the loop used to stop. Their array fast paths still hoist, because an array cannot change length underneath one.

Dataset Scenarios¶

• Sorted – ascending integers, verifying best-case behavior.
• Nearly Sorted (2% swaps) – deterministic neighbor swaps introduce light disorder to expose adaptive optimizations.
• Shuffled (deterministic) – Fisher–Yates shuffle using a fixed seed for reproducibility across runs and machines.

Each benchmark sorts a fresh copy of the dataset once and reports wall-clock duration. A cell reading pending means nobody has run this suite on that operating system, not that the algorithm is slow there.

Windows (Editor/Player)¶

Last updated 2026-09-14 05:19 UTC on Windows 11 (10.0.26200).

Times are single-pass measurements in milliseconds (lower is better). n/a indicates the algorithm was skipped for the dataset size.

Sorted¶

Nearly Sorted (2% swaps)¶

Shuffled (deterministic)¶

macOS¶

Pending: run the IList sorting benchmark suite on macOS to capture results.

Linux¶

Pending: run the IList sorting benchmark suite on Linux to capture results.

Other Platforms¶

Pending: run the IList sorting benchmark suite on the target platform to capture results.

Refreshing these numbers¶

Run IListSortingPerformanceTests.Benchmark from Unity's Test Runner. It rewrites the section matching the operating system it ran on and leaves the others alone.