Skip to content

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

Algorithm Stable? Best For Reference
Ghost Sort No Mixed workloads that benefit from adaptive gap sorting and few allocations Upstream project by Will Stafford Parsons (public repository currently offline)
Meteor Sort No Almost-sorted data where gap shrinking beats plain insertion sort Upstream project by Will Stafford Parsons (public repository currently offline)
Pattern-Defeating QuickSort No General-purpose quicksort with protections against worst-case inputs pdqsort by Orson Peters
Grail Sort Yes Large datasets where stability + low allocations matter GrailSort
Power Sort Yes Partially ordered data that benefits from adaptive run detection PowerSort (Munro & Wild)
Tim Sort Yes General-purpose stable sorting with abundant natural runs Wikipedia - Timsort
Jesse Sort No Data with long runs or duplicates where dual patience piles shine JesseSort
Green Sort Yes Sustainable stable merges that trim ordered prefixes greeNsort
Ska Sort No Branch-friendly partitioning on large unstable datasets Ska Sort
Ipn Sort No In-place adaptive quicksort scenarios needing robust pivots ipnsort write-up
Smooth Sort No Weak-heap hybrid that approaches O(n) for presorted data Smoothsort - Wikipedia
Block Merge Sort Yes Stable merges with √n buffer (WikiSort style) WikiSort
IPS⁴o Sort No Cache-aware samplesort with multiway partitioning IPS⁴o paper
Power Sort Plus Yes Enhanced run-priority merges inspired by Wild & Nebel PowerSort paper
Glide Sort Yes Stable galloping merges from the Rust glidesort research sort-research-rs
Flux Sort No Dual-pivot quicksort tuned for modern CPUs sort-research-rs
Insertion Sort Yes Tiny or nearly sorted collections where O(n²) is acceptable Wikipedia - Insertion sort

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.

Heads up: The original Ghost Sort repository was formerly hosted on GitHub under wstaffordp/ghostsort, but it currently returns 404. The Unity Helpers implementation remains based on that source; we will relink if/when an official mirror returns.

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. If a cell still shows pending, re-run the benchmark suite to collect fresh data for that algorithm/dataset size.

Run the IListSortingPerformanceTests.Benchmark test inside Unity’s Test Runner to refresh the tables below. Results automatically land in the section that matches the current operating system.

Windows (Editor/Player)

Last updated 2026-01-12 01:17 UTC on Windows 11 (10.0.26200) 64bit

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

Sorted

List Size Ghost Meteor Pattern-Defeating QuickSort Grail Power Insertion Tim Jesse Green Ska Ipn Smooth Block IPS4o Power+ Glide Flux
1000.029 ms0.002 ms0.001 ms0.001 ms0.002 ms0.001 ms0.001 ms0.624 ms0.001 ms0.007 ms0.001 ms0.002 ms0.001 ms0.001 ms0.001 ms0.002 ms0.002 ms
1,0000.023 ms0.027 ms0.008 ms0.007 ms0.007 ms0.006 ms0.006 ms54.3 ms0.007 ms0.112 ms0.009 ms0.018 ms0.005 ms0.040 ms0.007 ms0.007 ms0.029 ms
10,0000.305 ms0.394 ms0.077 ms0.066 ms0.049 ms0.066 ms0.047 ms3.24 s0.071 ms1.45 ms0.083 ms0.175 ms0.056 ms0.571 ms0.048 ms0.048 ms0.386 ms
100,0003.51 ms5.14 ms0.764 ms0.658 ms0.469 msn/a0.459 ms136.86 s0.670 ms18.5 ms0.773 ms1.80 ms0.512 ms7.57 ms0.473 ms0.479 ms4.93 ms

Nearly Sorted (2% swaps)

List Size Ghost Meteor Pattern-Defeating QuickSort Grail Power Insertion Tim Jesse Green Ska Ipn Smooth Block IPS4o Power+ Glide Flux
1000.001 ms0.002 ms0.002 ms0.001 ms0.003 ms0.001 ms0.002 ms241 ms0.001 ms0.007 ms0.002 ms0.002 ms0.001 ms0.002 ms0.004 ms0.003 ms0.002 ms
1,0000.023 ms0.031 ms0.033 ms0.007 ms0.018 ms0.007 ms0.014 ms2.43 s0.007 ms0.100 ms0.030 ms0.018 ms0.007 ms0.045 ms0.025 ms0.016 ms0.030 ms
10,0000.293 ms0.395 ms0.443 ms0.073 ms0.232 ms0.063 ms0.173 ms23.44 s0.071 ms1.44 ms0.405 ms0.189 ms0.069 ms0.674 ms0.433 ms0.166 ms0.390 ms
100,0003.60 ms5.19 ms5.30 ms0.843 ms3.53 msn/a2.43 ms137.09 s0.727 ms18.8 ms4.98 ms1.95 ms0.633 ms8.46 ms5.37 ms2.28 ms4.96 ms

Shuffled (deterministic)

List Size Ghost Meteor Pattern-Defeating QuickSort Grail Power Insertion Tim Jesse Green Ska Ipn Smooth Block IPS4o Power+ Glide Flux
1000.008 ms0.007 ms0.006 ms0.007 ms0.008 ms0.017 ms0.011 ms61.7 ms0.008 ms0.011 ms0.008 ms0.012 ms0.005 ms0.006 ms0.025 ms0.012 ms0.007 ms
1,0000.156 ms0.132 ms0.088 ms0.105 ms0.152 ms1.49 ms0.160 ms216 ms0.121 ms0.133 ms0.097 ms0.200 ms0.089 ms0.107 ms0.434 ms0.159 ms0.098 ms
10,0002.50 ms1.95 ms1.22 ms1.46 ms1.49 ms147 ms1.57 ms669 ms1.38 ms1.78 ms1.33 ms2.76 ms1.20 ms1.57 ms5.98 ms1.80 ms1.44 ms
100,00031.9 ms26.0 ms15.3 ms18.2 ms18.3 msn/a20.4 ms2.21 s18.3 ms23.0 ms15.9 ms35.5 ms15.2 ms20.2 ms77.1 ms23.6 ms17.6 ms

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.