[API proposal] Add optimized SortedArray [renamed to BinarySortedList] (I can't create own tools with high performance)

[RioMcBoo]

Description

I tried to create my own super-fast sorted array with binary search.

I was guided by existing solutions for List, but a wrapper is still needed to protect against incorrect actions. So I tried to create my own class based on List. But I failed, and here's why:

1. List has a reserve capacity for optimization, but since I use it instead of the base Array (because Array does not have tools for implementing binary search) - I had to create my own reserve capacity, which in total makes my class too cumbersome in memory.
2. Array.Copy and CopyTo require only T[] as arguments, otherwise manual iteration is much slower.

SortedArray achieves such good results due to:

• Centering of data, which reduces the number of elements to be shifted by half.
• Optimized binary search with preliminary check of boundary elements, which allows to quickly find the position for insertion, especially on an already sorted data set, regardless of the sorting direction.
• Universality when working with pre-sorted data, regardless of the sorting direction.
• High memory locality, which ensures efficient use of the cache.
• This structure is especially effective in scenarios where the data already has a preliminary order (for example, by the first column of a table)

What I got I present below (based on Array):

using System;

namespace CustomCollections.BinarySortedList
{
    [Flags]
    public enum BinarySortedListOptions
    {
        None = 0,
        DisallowDuplicates = 1,
        SkipDuplicates = 2,
        DisallowResize = 4,
    }

    public enum FindIndexOptions
    {
        Random = 0,
        First = 1,
        Last = 2,
    }

    public class BinarySortedList<T> : IReadOnlyList<T>, IReadOnlyCollection<T>, ICollection<T>
    {
        private enum ShiftOperation
        {
            MoveRight = 0,
            MoveLeft = 1,
            Center = 2,
            Resize = 3,
        }

        public int Capacity => _storage.Length;
        public int Count => _count;

        private int LeftBuffer => _zeroIndex;
        private int RightBuffer => Capacity - _zeroIndex - _count;
        private bool CanMoveLeft => LeftBuffer > 0;
        private bool CanMoveRight => RightBuffer > 0;

        public bool IsReadOnly => false;

        private int VIndex(int storageIndex) => storageIndex - _zeroIndex;
        private int SIndex(int virtualIndex) => virtualIndex + _zeroIndex;

        private const int DefaultCapacity = 4;
        private T[] _storage;
        private int _zeroIndex;
        private int _count;
        private int _version;
        BinarySortedListOptions_options = BinarySortedListOptions.None;
        private readonly IComparer<T> _comparer;

        public BinarySortedList(int capacity = DefaultCapacity, BinarySortedListOptions options = BinarySortedListOptions.None, IComparer<T> comparer = null)
        {
            _storage = new T[capacity];
            _zeroIndex = CalculateZeroIndex(capacity, 0);
            _comparer = comparer;
            _options = options;
            CheckOptions(ref _options);
        }

        public BinarySortedList(IEnumerable<T> initialValues, BinarySortedListOptions options = BinarySortedListOptions.None, IComparer<T> comparer = null)
        {
            _storage = new T[DefaultCapacity];
            _zeroIndex = CalculateZeroIndex(DefaultCapacity, 0);
            _comparer = comparer;
            _options = options;
            CheckOptions(ref _options);

            foreach (var item in initialValues)
            {
                Add(item);
            }
        }

        public BinarySortedList(IReadOnlyCollection<T> initialValues, BinarySortedListOptions options = BinarySortedListOptions.None, IComparer<T> comparer = null)
        {
            _storage = new T[initialValues.Count];
            _zeroIndex = CalculateZeroIndex(initialValues.Count, 0);
            _comparer = comparer;
            _options = options;
            CheckOptions(ref _options);

            foreach (var item in initialValues)
            {
                Add(item);
            }
        }

        private void CheckOptions(ref BinarySortedListOptions options)
        {
            if ((options & BinarySortedListOptions .DisallowDuplicates) > 0 && (options & BinarySortedListOptions.SkipDuplicates) > 0)
            {
                options &= ~BinarySortedListOptions.SkipDuplicates;
            }
        }

        private int CalculateZeroIndex(int capacity, int count)
        {
            if (capacity < 0 || count < 0 || capacity < count)
            {
                throw new ArgumentOutOfRangeException(nameof(CalculateZeroIndex), "capacity < 0 || count < 0 || capacity < count");
            }

            return (capacity - count) / 2;
        }

        private static (int left, int right) GetPartLengths(int insertIndex, int length, bool remove = false)
        {
            int leftPart = insertIndex;
            int rightPart = length - insertIndex - (remove ? 1 : 0);

            return (leftPart, rightPart);
        }

        private int Compare(ref T currentItem, ref T item)
        {
            if (_comparer != null)
            {
                return _comparer.Compare(currentItem, item);
            }
            else if (currentItem is IComparable<T> comparable)
            {
                return comparable.CompareTo(item);
            }
            else
            {
                return Comparer<T>.Default.Compare(currentItem, item);
            }
        }

        private int FindIndex(ref T item, int arrayStartIndex, int arrayEndIndex, FindIndexOptions indexOption = FindIndexOptions.Random)
        {
            int lo = arrayStartIndex;
            int hi = arrayEndIndex;
            int? index = null;

            while (lo <= hi)
            {
                //// PERF: `lo` or `hi` will never be negative inside the loop,
                //       so computing median using uints is safe since we know
                //       `length <= int.MaxValue`, and indices are >= 0
                //       and thus cannot overflow an uint.
                //       Saves one subtraction per loop compared to
                //       `int i = lo + (hi - lo) / 2;`
                int i = (int)(((uint)hi + (uint)lo) >> 1);

                int compareResult = Compare(ref _storage[SIndex(i)], ref item);

                if (compareResult == 0)
                {
                    index = i;

                    if (indexOption == FindIndexOptions.Random)
                    {
                        return i;
                    }

                    if (indexOption == FindIndexOptions.First)
                    {
                        hi = i - 1;
                    }
                    else if (indexOption == FindIndexOptions.Last)
                    {
                        lo = i + 1;
                    }
                }
                else if (compareResult > 0)
                {
                    hi = i - 1;
                }
                else
                {
                    lo = i + 1;
                }
            }

            if (index.HasValue)
            {
                return index.Value;
            }

            return ~lo;
        }

        private void CheckIndex(int index)
        {
            if (index < 0 || index >= Count)
            {
                throw new ArgumentOutOfRangeException(nameof(index), "Index out of range");
            }
        }

        private void MoveLeft(int startndex, int length)
        {
            Array.Copy(_storage, SIndex(startndex), _storage, SIndex(startndex - 1), length);
        }

        private void MoveRight(int startIndex, int length)
        {
            Array.Copy(_storage, SIndex(startIndex), _storage, SIndex(startIndex + 1), length);
        }

        private void Move(T[] srcArray, int srcIndex, int length, T[] destArray, int destIndex)
        {
            Array.Copy(srcArray, SIndex(srcIndex), destArray, SIndex(destIndex), length);
        }

        private void Center(int insertPlace, (int left, int right) parts)
        {
            int newCount = Count + 1;
            int newZeroIndex = CalculateZeroIndex(Capacity, newCount);

            int delta = newZeroIndex - _zeroIndex;
            ShiftOperation shiftDirection = delta >= 0 ? ShiftOperation.MoveRight : ShiftOperation.MoveLeft;

            if (shiftDirection == ShiftOperation.MoveRight)
            {
                // Move right part of the array to the right
                Move(_storage, insertPlace, parts.right, _storage, insertPlace + delta + /*reserve 1 place for new item*/ 1);
                // Move left part of the array to the right
                Move(_storage, 0, parts.left, _storage, 0 + delta);
            }
            else
            {
                // Move left part of the array to the left
                Move(_storage, 0, parts.left, _storage, 0 + delta);
                // Move right part of the array to the left
                Move(_storage, insertPlace, parts.right, _storage, insertPlace + delta + /*reserve 1 place for new item*/ 1);
            }

            _zeroIndex = newZeroIndex;
        }

        private void Resize(int insertPlace, (int left, int right) parts, int newCapacity)
        {
            // for first insertion
            newCapacity = newCapacity == 0 ? DefaultCapacity : newCapacity;

            T[] oldStorage = _storage;
            _storage = new T[newCapacity];

            int newCount = Count + 1;
            int newZeroIndex = CalculateZeroIndex(newCapacity, newCount);

            int delta = newZeroIndex - _zeroIndex;
            ShiftOperation shiftDirection = delta >= 0 ? ShiftOperation.MoveRight : ShiftOperation.MoveLeft;

            if (shiftDirection == ShiftOperation.MoveRight)
            {
                // Move right part of the array to the right
                Move(oldStorage, insertPlace, parts.right, _storage, insertPlace + delta + /*reserve 1 place for new item*/ 1);
                // Move left part of the array to the right
                Move(oldStorage, 0, parts.left, _storage, 0 + delta);
            }
            else
            {
                // Move left part of the array to the left
                Move(oldStorage, 0, parts.left, _storage, 0 + delta);
                // Move right part of the array to the left
                Move(oldStorage, insertPlace, parts.right, _storage, insertPlace + delta + /*reserve 1 place for new item*/ 1);
            }

            _zeroIndex = newZeroIndex;
        }

        public int FindRandomIndex(T item) => FindRandomIndex(ref item);
        public int FindFirstIndex(T item) => FindFirstIndex(ref item);
        public int FindLastIndex(T item) => FindLastIndex(ref item);

        public int FindRandomIndex(ref T item) => FindIndex(ref item, FindIndexOptions.Random);
        public int FindFirstIndex(ref T item) => FindIndex(ref item, FindIndexOptions.First);
        public int FindLastIndex(ref T item) => FindIndex(ref item, FindIndexOptions.Last);

        public int FindIndex(T item, FindIndexOptions findOption) => FindIndex(ref item, findOption);
        public int FindIndex(ref T item, FindIndexOptions findOption)
        {
            if (_count == 0)
                return ~_count;

            if (_count == 1)
                return FindIndex(ref item, 0, 0);

            int findResult;
            int currentIndex;
            int startIndex = 0;
            int endIndex = Count - 1;

            if (findOption != FindIndexOptions.Last)
            {
                // Try find item in the very low edge
                currentIndex = startIndex;
                startIndex++;
                findResult = FindIndex(ref item, currentIndex, currentIndex, findOption);

                if (findResult > -1 || findResult == ~currentIndex)
                {
                    return findResult;
                }
            }

            if (findOption != FindIndexOptions.First)
            {
                // Try find item in the very high edge
                currentIndex = endIndex;
                endIndex--;
                findResult = FindIndex(ref item, currentIndex, currentIndex, findOption);

                if (findResult > -1 || findResult == ~(currentIndex + 1))
                {
                    return findResult;
                }
            }

            // Try find item in the remains
            return FindIndex(ref item, startIndex, endIndex, findOption);
        }

        private ShiftOperation GetOperation(int insertPlace, (int left, int right) parts, BinarySortedListOptions options)
        {
            ShiftOperation operation;
            bool couldWeCenter = (Capacity - Count) >= DefaultCapacity;

            if (parts.left < parts.right)
            {
                // We should move the left part of the array to the edge
                operation = ShiftOperation.MoveLeft;

                if (!CanMoveLeft)
                {
                    if (couldWeCenter && (parts.right / (parts.left + 1)) >= 2)
                    {
                        // If we can't move left part and right part anyway is huge - then center all array                        
                        operation = ShiftOperation.Center;
                    }
                    else if (!CanMoveRight)
                    {
                        // We have no options
                        operation = ShiftOperation.Resize;
                    }
                    else
                    {
                        // in other way we can change the direction of the shift
                        operation = ShiftOperation.MoveRight;
                    }
                }
            }
            else
            {
                // We should move the right part of the array to the edge
                operation = ShiftOperation.MoveRight;

                if (!CanMoveRight)
                {
                    if (couldWeCenter && (parts.left / (parts.right + 1)) >= 2)
                    {
                        // If we can't move right part and left part anyway is huge - then center all array
                        operation = ShiftOperation.Center;
                    }
                    else if (!CanMoveLeft)
                    {
                        // We have no options
                        operation = ShiftOperation.Resize;
                    }
                    else
                    {
                        // in other way we can change the direction of the shift
                        operation = ShiftOperation.MoveLeft;
                    }
                }
            }

            return operation;
        }

        public void Add(T item) => Add(ref item);
        public void Add(ref T item)
        {
            if (TryAdd(ref item, out _))
            {
                return;
            }
            else
            {
                if ((_options & BinarySortedListOptions.DisallowDuplicates) > 0)
                    throw new ArgumentException("Item already exists in the array", nameof(item));
            }
        }

        public bool TryAdd(T item) => TryAdd(ref item, out _);
        public bool TryAdd(ref T item) => TryAdd(ref item, out _);
        public bool TryAdd(T item, out int index) => TryAdd(ref item, out index);
        public bool TryAdd(ref T item, out int index)
        {
            _version = unchecked(++_version);
            int currentVersion = _version;
            int findResult = FindRandomIndex(ref item);

            if (findResult > -1)
            {
                if ((_options & (BinarySortedListOptions.SkipDuplicates | BinarySortedListOptions.DisallowDuplicates)) > 0)
                {
                    index = ~findResult;
                    return false;
                }
            }

            int insertPlace = findResult < 0 ? ~findResult : findResult;

            var parts = GetPartLengths(insertPlace, Count);

            var operation = GetOperation(insertPlace, parts, _options);

            switch (operation)
            {
                case ShiftOperation.MoveLeft:
                    MoveLeft(0, parts.left);
                    _zeroIndex--;
                    break;
                case ShiftOperation.MoveRight:
                    MoveRight(insertPlace, parts.right);
                    break;
                case ShiftOperation.Center:
                    Center(insertPlace, parts);
                    break;
                case ShiftOperation.Resize:
                    if (_options.HasFlag(BinarySortedListOptions.DisallowResize))
                        throw new InvalidOperationException("Can't resize array");
                    else
                        Resize(insertPlace, parts, Capacity * 2);
                    break;
            }

            _count++;
            _storage[SIndex(insertPlace)] = item;

            if (currentVersion != _version)
                throw new Exception("SortedArray was changed");

            index = findResult;

            return true;
        }

        public T this[int index]
        {
            get
            {
                CheckIndex(index);
                return _storage[SIndex(index)];
            }
        }

        public void RemoveAt(int index)
        {
            _version = unchecked(++_version);

            CheckIndex(index);

            var parts = GetPartLengths(index, _count, true);

            ShiftOperation shiftDirection;

            if (parts.left < parts.right)
            {
                shiftDirection = ShiftOperation.MoveRight;
            }
            else
            {
                shiftDirection = ShiftOperation.MoveLeft;
            }

            switch (shiftDirection)
            {
                case ShiftOperation.MoveLeft:
                    MoveLeft(index + 1, parts.right);
                    break;
                case ShiftOperation.MoveRight:
                    MoveRight(0, parts.left);
                    _zeroIndex++;
                    break;
            }

            _count--;
        }

        public IEnumerator<T> GetEnumerator()
        {
            int currentVersion = _version;
            for (int i = 0; i < Count; i++)
            {
                if (currentVersion == _version)
                    yield return _storage[SIndex(i)];
                else
                    throw new Exception("SortedArray was changed");
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public void Clear()
        {
            _version = unchecked(++_version);
            _storage = new T[_storage.Length];
            _count = 0;
            _zeroIndex = CalculateZeroIndex(_storage.Length, _count);
        }

        public bool Contains(T item) => Contains(ref item);
        public bool Contains(ref T item) => FindRandomIndex(ref item) > -1;

        public void CopyTo(T[] array, int arrayIndex = 0)
        {
            // Delegate rest of error checking to Array.Copy.
            Array.Copy(_storage, _zeroIndex, array, arrayIndex, _count);
        }

        public void CopyTo(int index, T[] array, int arrayIndex, int count)
        {
            if (_count - index < count)
            {
                throw new ArgumentException("Not enough elements in the source array");
            }

            // Delegate rest of error checking to Array.Copy.
            Array.Copy(_storage, SIndex(index), array, arrayIndex, count);
        }

        public bool Remove(T item) => Remove(ref item);
        public bool Remove(ref T item)
        {
            int index = FindRandomIndex(ref item);
            if (index > -1)
            {
                RemoveAt(index);
                return true;
            }
            else
            {
                return false;
            }
        }
    }
}

end here:

using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

namespace CustomCollections.SortedList
{
    public class BenchmarkTests
    {
        private const int Count = 10000;
        private Random _random;
        private List<int> _initialListUnsorted;
        private List<int> _initialListSorted;
        private List<int> _initialListSortedUnique;

        [GlobalSetup]
        public void Setup()
        {
            _random = new Random(9873);
            _initialListUnsorted = new();

            for (int i = 0; i < Count; i++)
            {
                int r = _random.Next();
                _initialListUnsorted.Add(r);
            }

            _initialListSorted = new(_initialListUnsorted);   
            _initialListSorted.Sort();


            _initialListSortedUnique = new();
            foreach(var i in _initialListSorted)
            {
                var index = _initialListSortedUnique.BinarySearch(i);
                if (index < 0)
                {
                    index = ~index;
                    _initialListSortedUnique.Insert(index, i);
                }
            }
        }

        [Benchmark]
        public void CreateSortedArray()
        {
            var sortedArray = new SortedArray<int>(0);
            for (int i = 0; i < _initialListUnsorted.Count; i++)
            {
                int r = _initialListUnsorted[i];
                sortedArray.Add(r, BinarySortedListOptions.SkipDuplicates);
            }
        }

        [Benchmark]
        public void CreateSortedList()
        {
            var sortedList = new SortedList<int, int>(0);
            for (int i = 0; i < _initialListUnsorted.Count; i++)
            {
                int r = _initialListUnsorted[i];
                if (!sortedList.ContainsKey(r))
                {
                    sortedList.Add(r, r);
                }
            }
        }

        [Benchmark]
        public void CreateSortedDictionary()
        {
            var sortedDictionary = new SortedDictionary<int, int>();
            for (int i = 0; i < _initialListUnsorted.Count; i++)
            {
                int r = _initialListUnsorted[i];
                if (!sortedDictionary.ContainsKey(r))
                {
                    sortedDictionary.Add(r, r);
                }
            }
        }

        [Benchmark]
        public void CreateList()
        {
            var list = new List<int>(0);
            for (int i = 0; i < _initialListUnsorted.Count; i++)
            {
                int r = _initialListUnsorted[i];
                var index = list.BinarySearch(r);
                if (index < 0)
                {
                    index = ~index;
                    list.Insert(index, r);
                }
            }
        }

        [Benchmark]
        public void ManualCopyInSortedArrayFromSorted()
        {
            var sortedArray = new SortedArray<int>(0);
            for (int i = 0; i < _initialListSorted.Count; i++)
            {
                int r = _initialListSorted[i];
                sortedArray.Add(i, BinarySortedListOptions.SkipDuplicates);
            }
        }

        [Benchmark]
        public void ManualCopyInSortedListFromSorted()
        {
            var sortedList = new SortedList<int,int>(0);
            for (int i = 0; i < _initialListSorted.Count; i++)
            {
                int r = _initialListSorted[i];
                if (!sortedList.ContainsKey(r))
                {
                    sortedList.Add(r, r);
                }
            }
        }

        [Benchmark]
        public void ManualCopyInSortedDictionaryFromSorted()
        {
            var sortedDictionary = new SortedDictionary<int, int>();
            for (int i = 0; i < _initialListSorted.Count; i++)
            {
                int r = _initialListSorted[i];
                if (!sortedDictionary.ContainsKey(r))
                {
                    sortedDictionary.Add(r, r);
                }
            }
        }

        [Benchmark]
        public void ManualCopyInListFromSorted()
        {
            var sortedList = new List<int>(0);
            for (int i = 0; i < _initialListSorted.Count; i++)
            {
                int r = _initialListSorted[i];
                var index = sortedList.BinarySearch(i);
                if (index < 0)
                {
                    index = ~index;
                    sortedList.Insert(index, i);
                }
            }
        }

        [Benchmark]
        public void ManualCopyInSortedArrayFromSortedUnique()
        {
            var sortedArray = new SortedArray<int>(0);
            for (int i = 0; i < _initialListSorted.Count; i++)
            {
                int r = _initialListSorted[i];
                sortedArray.Add(i);
            }
        }

        [Benchmark]
        public void ManualCopyInSortedListFromSortedUnique()
        {
            var sortedList = new SortedList<int, int>(0);
            for (int i = 0; i < _initialListSorted.Count; i++)
            {
                int r = _initialListSorted[i];                
                {
                    sortedList.Add(r, r);
                }
            }
        }

        [Benchmark]
        public void ManualCopyInSortedDictionaryFromSortedUnique()
        {
            var sortedDictionary = new SortedDictionary<int, int>();
            for (int i = 0; i < _initialListSorted.Count; i++)
            {
                int r = _initialListSorted[i];                
                {
                    sortedDictionary.Add(r, r);
                }
            }
        }

        [Benchmark]
        public void ManualCopyInListFromSortedUnique()
        {
            var sortedList = new List<int>(0);
            for (int i = 0; i < _initialListSorted.Count; i++)
            {
                int r = _initialListSorted[i];
                var index = sortedList.BinarySearch(i);
                if (index < 0)
                {
                    index = ~index;                    
                }
                sortedList.Insert(index, i);
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            BenchmarkRunner.Run<BenchmarkTests>();
        }
    }
}

Why did I even decide to make such a list? I like the idea of ​​binary search, it gives stable logarithmic speed and as it turned out, working with regular arrays is quite fast for small values ​​of elements in the list (up to 50,000). If the base for such a sorted list is an array, you can easily move through it page by page (via offset). Another distinctive feature is that such a list supports duplicates, which hash tables cannot do.

I wanted to speed up the work of the existing List or Array by placing elements not from the beginning of the array, but from the middle. Thus, the speed of copying data when adding/removing is reduced by 2 times. However, the increase is visible in my implementation only with the number of elements above 50,000.

Nevertheless, when filling an array from an already sorted list, List performs simply lightning fast. And my SortedArray cannot compete with it in this at all.

That is why I have a request to add such a SortedArray and optimize it in the same way as List + BinarySearch (you can also add IReadOnlyList implementation)

Configuration

Win x64, VS Version 17.13.6, Legion 7 15IMH05

[AaronRobinsonMSFT]

That is why I have a request to add such a SortedArray and optimize it in the same way as List + BinarySearch (you can also add IReadOnlyList implementation)

This sounds like a new API proposal. I would create a new issue using the "API Suggestion" template in github. Simply go back to the issues page, select "New issue" and then select "API Suggestion. This will prompt you with a template that will help guide you through the API proposal process.

[dotnet-policy-service]

Tagging subscribers to this area: @dotnet/area-system-collections
See info in area-owners.md if you want to be subscribed.

[colejohnson66]

Do not use Stopwatch to benchmark - JIT tiering will mess with the numbers. Use BenchmarkDotNet

[timcassell]

(because Array does not have tools for implementing binary search)

You can use array.AsSpan(...).BinarySearch(...) using MemoryExtensions.

[RioMcBoo]

But it causes boxing for value types =(

[huoyaoyuan]

But it causes boxing for value types =(

It will no longer be the case since .NET 10. The boxing overload is deprioritized now.
With .NET 9, you can still manually pick the better overload with manually specifying generic parameter twice: span.BinarySearch<T, T>(item)

[RioMcBoo]

probably due to some optimizations the memoryExtensions version does not work, because when comparing it always compares the inserted object with a zero value

Anyway, the main problem is in coping of array, i did couple changes and the result now is better, but List below 50000 items always extra fast, especially when fills from already sorted list - it is literally a milliseconds

[RioMcBoo]

I updated the code:

• fixed bugs
• refactored
• did improvements

All list of improvements:

1. Placing elements not from the beginning of the array, but from the middle. Thus, the speed of copying data when adding/removing is reduced by 2 times.
2. The search occurs first at the array boundaries, which speeds up copying from an already sorted array.
3. Simultaneous insertion of an element when resizing an array (this compensates with the counterweight of the centering operation)

After I made the search to be performed first from the ends of the array - the speed of copying from a sorted array increased several times, but relative to the time of copying from an unsorted one - the difference did not change much, which proves the fact that I cannot do further optimization on my own (or I can do it by resorting to unsafe code, which I do not want to do), and everything depends on the speed of copying the array.

It seems to me that if something similar is added to the library, even in the form of auxiliary, but optimized methods - this will allow creating a very fast and straightforward array with sorting and the ability to store duplicates, and without any keys and values.

[RioMcBoo]

As a result, I conducted testing for the most ideal use cases of SortedArray, which are:

1. Sorting from an already pre-sorted array of data. For example, you have a selection of tabular data with columns, sorted by at least one of the columns. If you want to get a deeper sort by all columns - you can use SortedArray, which shows the best results in ideal cases (4 to 5 times the speed increase). The only condition is that the pre-sorting is performed by the same column as in the required final result.

For example, you can save a cache with an array already sorted once by a specific first field (the other fields do not play a big role). In the future, using this cache, you can achieve fast sorting by other fields.

As will be seen from the test results - hash tables with pre-sorted data work even worse than unsorted ones due to tree redistribution.

Later I will post a more realistic case, trying to match the number of variations in the columns close to my actual case.

`BenchmarkDotNet v0.14.0, Windows 11 (10.0.26100.3775)
Intel Core i7-10750H CPU 2.60GHz, 1 CPU, 12 logical and 6 physical cores
.NET SDK 9.0.203
[Host] : .NET 9.0.4 (9.0.425.16305), X64 RyuJIT AVX2 [AttachedDebugger]
DefaultJob : .NET 9.0.4 (9.0.425.16305), X64 RyuJIT AVX2

Method	PreSortScenario	TotalElements	Mean	Error	StdDev	Median	Gen0	Gen1	Gen2	Allocated
DynamicFill_List	Unsorted	100	14.781 us	0.2916 us	0.6022 us	14.500 us	9.6741	0.0305	-	59.35 KB
DynamicFill_SortedArray	Unsorted	100	15.872 us	0.1247 us	0.1166 us	15.857 us	12.5427	0.0305	-	76.87 KB
DynamicFill_SortedDictionary	Unsorted	100	12.965 us	0.1538 us	0.1363 us	12.908 us	10.6812	0.2289	-	65.52 KB
DynamicFill_SortedDictionaryToList	Unsorted	100	13.492 us	0.0723 us	0.0804 us	13.519 us	10.8643	0.2289	-	66.62 KB
DynamicFill_SortedList	Unsorted	100	14.737 us	0.0951 us	0.0843 us	14.701 us	10.2234	0.0763	-	62.67 KB
DynamicFill_List	Unsorted	500	107.943 us	0.5226 us	0.5808 us	107.896 us	68.4814	0.9766	-	420.02 KB
DynamicFill_SortedArray	Unsorted	500	120.379 us	1.1027 us	0.9208 us	120.293 us	84.9609	1.2207	-	521.76 KB
DynamicFill_SortedDictionary	Unsorted	500	115.456 us	0.6806 us	0.5683 us	115.336 us	74.3408	7.2021	-	455.98 KB
DynamicFill_SortedDictionaryToList	Unsorted	500	121.895 us	0.5831 us	0.5169 us	121.791 us	75.0732	7.3242	-	460.24 KB
DynamicFill_SortedList	Unsorted	500	122.345 us	2.3621 us	2.8119 us	121.381 us	70.5566	1.7090	-	432.44 KB
DynamicFill_List	Unsorted	1000	268.547 us	5.3326 us	12.1451 us	266.365 us	154.7852	4.3945	-	949.04 KB
DynamicFill_SortedArray	Unsorted	1000	330.396 us	6.5774 us	17.6696 us	329.581 us	188.9648	5.3711	-	1157.74 KB
DynamicFill_SortedDictionary	Unsorted	1000	319.776 us	6.1986 us	7.1383 us	320.512 us	166.0156	29.2969	-	1017.95 KB
DynamicFill_SortedDictionaryToList	Unsorted	1000	375.530 us	12.0715 us	34.2449 us	361.698 us	167.4805	29.7852	-	1026.13 KB
DynamicFill_SortedList	Unsorted	1000	363.528 us	16.7821 us	49.4823 us	353.787 us	158.6914	8.3008	-	973.5 KB
DynamicFill_List	Unsorted	5000	2,449.738 us	39.2671 us	34.8093 us	2,439.296 us	980.4688	121.0938	-	6006.95 KB
DynamicFill_SortedArray	Unsorted	5000	2,127.910 us	23.6417 us	20.9577 us	2,123.434 us	1152.3438	128.9063	-	7083.1 KB
DynamicFill_SortedDictionary	Unsorted	5000	2,643.296 us	186.5292 us	544.1144 us	2,369.859 us	1039.0625	3.9063	-	6368.36 KB
DynamicFill_SortedDictionaryToList	Unsorted	5000	2,453.660 us	53.5691 us	150.2135 us	2,396.424 us	1042.9688	359.3750	-	6407.84 KB
DynamicFill_SortedList	Unsorted	5000	3,073.773 us	27.2924 us	25.5294 us	3,069.123 us	1011.7188	246.0938	-	6199.55 KB
DynamicFill_List	Unsorted	10000	7,174.650 us	49.0908 us	40.9931 us	7,166.038 us	2132.8125	250.0000	-	13099.06 KB
DynamicFill_SortedArray	Unsorted	10000	5,588.537 us	30.6762 us	28.6945 us	5,588.330 us	2484.3750	250.0000	-	15262.07 KB
DynamicFill_SortedDictionary	Unsorted	10000	6,155.635 us	81.2380 us	75.9901 us	6,150.328 us	2257.8125	648.4375	171.8750	13849.89 KB
DynamicFill_SortedDictionaryToList	Unsorted	10000	6,744.763 us	117.7450 us	212.3186 us	6,674.427 us	2265.6250	539.0625	171.8750	13928.44 KB
DynamicFill_SortedList	Unsorted	10000	9,723.430 us	114.7439 us	89.5845 us	9,741.023 us	2171.8750	515.6250	31.2500	13483.72 KB
DynamicFill_List	Unsorted	50000	133,594.952 us	607.2063 us	567.9812 us	133,508.075 us	12500.0000	-	-	78197.68 KB
DynamicFill_SortedArray	Unsorted	50000	81,164.389 us	1,532.0596 us	1,358.1309 us	81,151.179 us	14428.5714	-	-	89098.8 KB
DynamicFill_SortedDictionary	Unsorted	50000	57,438.002 us	1,139.8914 us	1,774.6737 us	56,866.183 us	13888.8889	1888.8889	555.5556	82166.79 KB
DynamicFill_SortedDictionaryToList	Unsorted	50000	64,170.020 us	1,947.5785 us	5,556.5515 us	63,016.789 us	13888.8889	1888.8889	555.5556	82557.84 KB
DynamicFill_SortedList	Unsorted	50000	230,626.529 us	4,569.6635 us	11,464.3931 us	227,083.567 us	12666.6667	666.6667	333.3333	79734.63 KB
DynamicFill_List	Unsorted	100000	610,339.708 us	4,985.5821 us	4,163.1868 us	610,528.900 us	27000.0000	-	-	167331.16 KB
DynamicFill_SortedArray	Unsorted	100000	332,422.457 us	4,236.8677 us	3,755.8728 us	331,696.350 us	30000.0000	-	-	189191.74 KB
DynamicFill_SortedDictionary	Unsorted	100000	157,001.559 us	3,073.3513 us	5,134.8800 us	155,564.913 us	28750.0000	3250.0000	250.0000	175625.96 KB
DynamicFill_SortedDictionaryToList	Unsorted	100000	165,012.259 us	2,386.3083 us	1,992.6755 us	164,551.800 us	29000.0000	4000.0000	333.3333	176407.71 KB
DynamicFill_SortedList	Unsorted	100000	922,878.129 us	11,781.3688 us	10,443.8765 us	921,803.500 us	27000.0000	-	-	170403.67 KB
DynamicFill_List	Unsorted	500000	15,646,505.120 us	302,539.8047 us	282,995.9212 us	15,701,567.100 us	156000.0000	1000.0000	-	963549.6 KB
DynamicFill_SortedArray	Unsorted	500000	7,730,929.033 us	148,077.1969 us	158,440.9419 us	7,728,382.000 us	174000.0000	-	-	1072917.07 KB
DynamicFill_SortedDictionary	Unsorted	500000	1,407,587.375 us	27,895.9901 us	49,585.0980 us	1,402,598.600 us	165000.0000	33000.0000	1000.0000	1007596.28 KB
DynamicFill_SortedDictionaryToList	Unsorted	500000	1,376,923.708 us	14,998.6598 us	11,709.9670 us	1,380,542.550 us	165000.0000	33000.0000	1000.0000	1011503.04 KB
DynamicFill_SortedList	Unsorted	500000	22,152,404.019 us	440,264.5624 us	432,398.6692 us	22,070,264.000 us	156000.0000	2000.0000	-	975838.48 KB
DynamicFill_List	Ascending	100	9.846 us	0.0986 us	0.0874 us	9.828 us	10.3607	0.0305	-	63.51 KB
DynamicFill_SortedArray	Ascending	100	4.975 us	0.0331 us	0.0310 us	4.971 us	3.6545	0.0076	-	22.4 KB
DynamicFill_SortedDictionary	Ascending	100	16.740 us	0.2243 us	0.3558 us	16.664 us	14.6179	0.3052	-	89.58 KB
DynamicFill_SortedDictionaryToList	Ascending	100	17.382 us	0.0920 us	0.0815 us	17.383 us	14.8010	0.3052	-	90.68 KB
DynamicFill_SortedList	Ascending	100	10.420 us	0.0840 us	0.0702 us	10.434 us	10.8948	0.0763	-	66.83 KB
DynamicFill_List	Ascending	500	66.902 us	0.8551 us	0.7999 us	66.746 us	71.7773	1.0986	-	440.26 KB
DynamicFill_SortedArray	Ascending	500	24.275 us	0.1021 us	0.0853 us	24.251 us	18.4326	0.2747	-	113.02 KB
DynamicFill_SortedDictionary	Ascending	500	123.695 us	0.7284 us	0.6813 us	123.752 us	105.2246	10.0098	-	645.86 KB
DynamicFill_SortedDictionaryToList	Ascending	500	134.738 us	2.3135 us	2.0508 us	134.843 us	105.9570	10.0098	-	650.12 KB
DynamicFill_SortedList	Ascending	500	68.993 us	0.8037 us	1.1001 us	68.785 us	73.8525	1.9531	-	452.67 KB
DynamicFill_List	Ascending	1000	148.688 us	0.8030 us	0.7119 us	148.694 us	161.3770	4.8828	-	989.73 KB
DynamicFill_SortedArray	Ascending	1000	49.218 us	0.6886 us	0.5750 us	49.129 us	36.9263	1.0986	-	226.3 KB
DynamicFill_SortedDictionary	Ascending	1000	294.639 us	3.7006 us	2.8892 us	293.886 us	237.7930	46.8750	-	1459.61 KB
DynamicFill_SortedDictionaryToList	Ascending	1000	307.339 us	1.9902 us	1.8616 us	306.774 us	239.2578	41.5039	-	1467.79 KB
DynamicFill_SortedList	Ascending	1000	154.388 us	1.1324 us	1.0592 us	154.129 us	165.5273	8.5449	-	1014.19 KB
DynamicFill_List	Ascending	5000	1,022.904 us	6.1663 us	5.7680 us	1,023.540 us	1019.5313	125.0000	-	6252.6 KB
DynamicFill_SortedArray	Ascending	5000	265.014 us	1.5863 us	2.2750 us	264.578 us	184.5703	22.9492	-	1132.55 KB
DynamicFill_SortedDictionary	Ascending	5000	2,291.612 us	21.3044 us	18.8858 us	2,289.787 us	1500.0000	7.8125	-	9189.8 KB
DynamicFill_SortedDictionaryToList	Ascending	5000	2,302.138 us	16.2356 us	14.3924 us	2,301.250 us	1503.9063	7.8125	-	9229.28 KB
DynamicFill_SortedList	Ascending	5000	1,077.025 us	4.8614 us	4.3095 us	1,076.886 us	1050.7813	259.7656	-	6445.2 KB
DynamicFill_List	Ascending	10000	2,218.566 us	17.7867 us	16.6377 us	2,214.751 us	2218.7500	250.0000	-	13598.79 KB
DynamicFill_SortedArray	Ascending	10000	552.818 us	6.2799 us	5.2440 us	553.787 us	369.1406	73.2422	-	2265.37 KB
DynamicFill_SortedDictionary	Ascending	10000	5,546.724 us	36.9837 us	30.8831 us	5,531.719 us	3265.6250	359.3750	132.8125	20028.25 KB
DynamicFill_SortedDictionaryToList	Ascending	10000	5,825.275 us	108.6852 us	193.1878 us	5,740.178 us	3281.2500	367.1875	117.1875	20106.8 KB
DynamicFill_SortedList	Ascending	10000	2,361.560 us	16.3081 us	15.2546 us	2,364.862 us	2257.8125	527.3438	39.0625	13983.45 KB
DynamicFill_List	Ascending	50000	13,909.706 us	155.8518 us	138.1586 us	13,900.412 us	13109.3750	125.0000	125.0000	80722.84 KB
DynamicFill_SortedArray	Ascending	50000	3,244.646 us	50.2919 us	41.9960 us	3,232.070 us	1785.1563	125.0000	125.0000	11327.91 KB
DynamicFill_SortedDictionary	Ascending	50000	37,429.355 us	715.3912 us	765.4606 us	37,046.808 us	19692.3077	846.1538	230.7692	119419.02 KB
DynamicFill_SortedDictionaryToList	Ascending	50000	39,465.805 us	764.3021 us	993.8087 us	39,469.357 us	19642.8571	785.7143	214.2857	119810.1 KB
DynamicFill_SortedList	Ascending	50000	16,125.021 us	258.6804 us	241.9698 us	16,132.214 us	13140.6250	984.3750	484.3750	82259.7 KB
DynamicFill_List	Ascending	100000	34,085.389 us	401.2894 us	335.0948 us	33,981.733 us	28200.0000	200.0000	200.0000	172382.99 KB
DynamicFill_SortedArray	Ascending	100000	9,833.240 us	196.1818 us	527.0296 us	9,705.638 us	3750.0000	187.5000	187.5000	22657.6 KB
DynamicFill_SortedDictionary	Ascending	100000	83,814.553 us	1,598.9154 us	1,777.1902 us	83,349.514 us	41857.1429	1428.5714	285.7143	255257.52 KB
DynamicFill_SortedDictionaryToList	Ascending	100000	84,350.305 us	1,662.3275 us	2,954.7857 us	83,495.067 us	41833.3333	1333.3333	166.6667	256039.26 KB
DynamicFill_SortedList	Ascending	100000	42,609.225 us	820.8756 us	1,676.8315 us	43,290.442 us	28750.0000	1500.0000	750.0000	175455.96 KB
DynamicFill_List	Ascending	500000	259,425.505 us	4,939.7293 us	9,517.1820 us	255,015.000 us	160000.0000	-	-	985625.11 KB
DynamicFill_SortedArray	Ascending	500000	64,836.735 us	1,253.7643 us	1,287.5236 us	64,725.012 us	17875.0000	125.0000	125.0000	113329.98 KB
DynamicFill_SortedDictionary	Ascending	500000	521,847.269 us	10,066.0351 us	8,405.5952 us	520,687.800 us	239000.0000	5000.0000	-	1467590.64 KB
DynamicFill_SortedDictionaryToList	Ascending	500000	468,255.765 us	9,354.1460 us	15,105.2034 us	463,049.600 us	239000.0000	5000.0000	-	1471497.4 KB
DynamicFill_SortedList	Ascending	500000	270,670.050 us	5,267.7374 us	5,409.5785 us	271,420.500 us	160500.0000	1000.0000	500.0000	997914 KB
DynamicFill_List	Descending	100	11.626 us	0.0914 us	0.0811 us	11.604 us	8.6975	0.0153	-	53.34 KB
DynamicFill_SortedArray	Descending	100	3.215 us	0.0527 us	0.0628 us	3.191 us	1.9035	0.0038	-	11.68 KB
DynamicFill_SortedDictionary	Descending	100	19.074 us	0.1191 us	0.1056 us	19.082 us	14.6179	0.3052	-	89.58 KB
DynamicFill_SortedDictionaryToList	Descending	100	18.267 us	0.1522 us	0.1423 us	18.264 us	14.8010	0.3052	-	90.68 KB
DynamicFill_SortedList	Descending	100	13.892 us	0.2075 us	0.2470 us	13.793 us	9.2468	0.0610	-	56.66 KB
DynamicFill_List	Descending	500	92.959 us	1.1602 us	2.2629 us	92.198 us	62.9883	0.8545	-	386.55 KB
DynamicFill_SortedArray	Descending	500	15.375 us	0.0912 us	0.0853 us	15.389 us	9.5520	0.1221	-	58.55 KB
DynamicFill_SortedDictionary	Descending	500	134.292 us	2.6754 us	2.9737 us	133.296 us	105.2246	10.0098	-	645.86 KB
DynamicFill_SortedDictionaryToList	Descending	500	139.326 us	1.1430 us	0.9545 us	139.380 us	105.9570	10.0098	-	650.12 KB
DynamicFill_SortedList	Descending	500	109.060 us	1.4128 us	1.1798 us	108.655 us	64.9414	1.7090	-	398.97 KB
DynamicFill_List	Descending	1000	235.143 us	1.2136 us	1.0134 us	235.059 us	143.7988	4.1504	-	881.45 KB
DynamicFill_SortedArray	Descending	1000	30.597 us	0.1562 us	0.1304 us	30.580 us	19.1040	0.5493	-	117.15 KB
DynamicFill_SortedDictionary	Descending	1000	317.858 us	6.1300 us	8.1834 us	315.959 us	237.7930	46.8750	-	1459.61 KB
DynamicFill_SortedDictionaryToList	Descending	1000	328.282 us	3.6099 us	3.3767 us	328.007 us	239.2578	41.5039	-	1467.79 KB
DynamicFill_SortedList	Descending	1000	298.949 us	4.6034 us	3.8440 us	298.339 us	147.4609	7.3242	-	905.91 KB
DynamicFill_List	Descending	5000	3,090.633 us	15.5091 us	14.5072 us	3,090.849 us	929.6875	113.2813	-	5707.15 KB
DynamicFill_SortedArray	Descending	5000	167.518 us	2.2102 us	1.9593 us	167.034 us	95.4590	11.7188	-	585.9 KB
DynamicFill_SortedDictionary	Descending	5000	2,353.666 us	20.4666 us	18.1431 us	2,349.623 us	1500.0000	7.8125	-	9189.8 KB
DynamicFill_SortedDictionaryToList	Descending	5000	2,403.590 us	15.0033 us	14.0341 us	2,400.524 us	1503.9063	7.8125	-	9229.27 KB
DynamicFill_SortedList	Descending	5000	4,294.131 us	55.0860 us	79.0026 us	4,269.311 us	960.9375	218.7500	-	5899.75 KB
DynamicFill_List	Descending	10000	10,847.026 us	45.6128 us	35.6115 us	10,852.888 us	2031.2500	250.0000	-	12506.57 KB
DynamicFill_SortedArray	Descending	10000	350.541 us	5.1354 us	4.2883 us	350.524 us	190.9180	38.0859	-	1171.84 KB
DynamicFill_SortedDictionary	Descending	10000	5,793.969 us	108.4923 us	137.2080 us	5,747.238 us	3265.6250	359.3750	132.8125	20028.25 KB
DynamicFill_SortedDictionaryToList	Descending	10000	5,977.192 us	40.9422 us	36.2942 us	5,975.594 us	3281.2500	343.7500	109.3750	20106.8 KB
DynamicFill_SortedList	Descending	10000	15,178.441 us	92.6684 us	77.3823 us	15,176.050 us	2078.1250	500.0000	31.2500	12891.24 KB
DynamicFill_List	Descending	50000	262,876.892 us	4,166.3616 us	4,630.8998 us	261,488.700 us	12000.0000	-	-	75255.82 KB
DynamicFill_SortedArray	Descending	50000	2,284.843 us	25.0199 us	23.4036 us	2,273.620 us	890.6250	125.0000	125.0000	5859.38 KB
DynamicFill_SortedDictionary	Descending	50000	38,227.617 us	760.0768 us	1,248.8281 us	37,706.586 us	19642.8571	785.7143	214.2857	119419.01 KB
DynamicFill_SortedDictionaryToList	Descending	50000	40,705.627 us	805.1930 us	1,018.3114 us	40,494.062 us	19692.3077	846.1538	230.7692	119810.08 KB
DynamicFill_SortedList	Descending	50000	419,262.046 us	4,518.0920 us	3,772.8114 us	418,693.000 us	12000.0000	-	-	76792.64 KB
DynamicFill_List	Descending	100000	1,185,466.879 us	23,249.1257 us	25,841.3416 us	1,200,466.700 us	26000.0000	-	-	161447.34 KB
DynamicFill_SortedArray	Descending	100000	6,649.994 us	131.0854 us	279.3537 us	6,657.105 us	1976.5625	195.3125	195.3125	11718.78 KB
DynamicFill_SortedDictionary	Descending	100000	85,675.627 us	1,587.9652 us	2,609.0725 us	85,320.086 us	41857.1429	1428.5714	285.7143	255257.63 KB
DynamicFill_SortedDictionaryToList	Descending	100000	85,597.815 us	1,110.7854 us	927.5561 us	85,437.433 us	41833.3333	1333.3333	166.6667	256039.32 KB
DynamicFill_SortedList	Descending	100000	1,729,461.447 us	22,807.7112 us	21,334.3472 us	1,726,154.100 us	26000.0000	-	-	164520.17 KB
DynamicFill_List	Descending	500000	29,798,715.767 us	347,867.4971 us	325,395.4728 us	29,773,262.700 us	151000.0000	3000.0000	-	930941.63 KB
DynamicFill_SortedArray	Descending	500000	57,749.589 us	1,488.5482 us	4,389.0182 us	57,886.761 us	9000.0000	111.1111	111.1111	58649.9 KB
DynamicFill_SortedDictionary	Descending	500000	456,951.508 us	3,958.2213 us	3,090.3188 us	456,214.500 us	239000.0000	5000.0000	-	1467590.2 KB
DynamicFill_SortedDictionaryToList	Descending	500000	478,480.314 us	7,494.9981 us	6,644.1206 us	476,717.900 us	239000.0000	5000.0000	-	1471496.63 KB
DynamicFill_SortedList	Descending	500000	43,633,083.546 us	274,471.3669 us	229,196.0223 us	43,666,562.900 us	151000.0000	4000.0000	-	943230.19 KB

using System;
using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;
using CustomCollections.SortedList;

// Enum for pre-sort scenarios.
public enum PreSortScenario
{
    Unsorted,
    Ascending,
    Descending
}

public class Program
{
    public static void Main(string[] args)
    {
        var summary = BenchmarkRunner.Run<DynamicSortBenchmarks>();
    }
}

// Test structure with 8 fields.
public class TestStructure
{
    public int Field1 { get; set; }
    public int Field2 { get; set; }
    public int Field3 { get; set; }
    public int Field4 { get; set; }
    public int Field5 { get; set; }
    public int Field6 { get; set; }
    public int Field7 { get; set; }
    public int Field8 { get; set; }
}

// Custom IComparer for cascading sorting across all 8 fields.
// Each field is compared with a specified direction (true for ascending, false for descending).
public class CustomComparer : IComparer<TestStructure>
{
    private readonly List<bool> directions;
    public CustomComparer(List<bool> directions)
    {
        this.directions = directions;
    }

    public int Compare(TestStructure x, TestStructure y)
    {
        int[] xValues = { x.Field1, x.Field2, x.Field3, x.Field4, x.Field5, x.Field6, x.Field7, x.Field8 };
        int[] yValues = { y.Field1, y.Field2, y.Field3, y.Field4, y.Field5, y.Field6, y.Field7, y.Field8 };

        for (int i = 0; i < directions.Count; i++)
        {
            int cmp = xValues[i].CompareTo(yValues[i]);
            if (cmp != 0)
                return directions[i] ? cmp : -cmp;
        }
        return 0;
    }
}

[MemoryDiagnoser]
public class DynamicSortBenchmarks
{
    // Parameter specifying the pre-sort scenario based on the first field:
    // Unsorted – original unsorted array,
    // Ascending – sorted in ascending order by the first field,
    // Descending – sorted in descending order by the first field.
    [Params(PreSortScenario.Unsorted, PreSortScenario.Ascending, PreSortScenario.Descending)]
    public PreSortScenario PreSortScenario;

    // Parameter specifying the total number of elements.
    [Params(100, 500, 1000, 5000, 10000, 50000, 100000, 500000)]
    public int TotalElements;

    // The base list that will be pre-sorted as per the selected scenario.
    public List<TestStructure> BaseList;

    // Custom comparer for dynamic insertion – uses cascading comparison across all 8 fields.
    // For example: Field1 ascending, Field2 descending, Field3 ascending, etc.
    public CustomComparer DynamicComparer = new CustomComparer(
        new List<bool> { true, false, true, false, true, false, true, false }
    );

    [GlobalSetup]
    public void Setup()
    {
        // Generate the original set of random data.
        var original = GenerateRandomData(TotalElements);

        // Create the base list according to the selected scenario.
        switch (PreSortScenario)
        {
            case PreSortScenario.Ascending:
                BaseList = original.OrderBy(x => x.Field1).ToList();
                break;
            case PreSortScenario.Descending:
                BaseList = original.OrderByDescending(x => x.Field1).ToList();
                break;
            case PreSortScenario.Unsorted:
            default:
                BaseList = original.ToList();
                break;
        }
    }

    // Method to generate the original random data.
    // Uses a HashSet to ensure unique elements, then converts it to a List.
    public HashSet<TestStructure> GenerateRandomData(int count)
    {
        Random rnd = new Random(42); // Fixed seed for reproducibility
        var set = new HashSet<TestStructure>(count);
        int i = 0;
        for (;i < count;)
        {
            var item = new TestStructure
            {
                Field1 = rnd.Next(),
                Field2 = rnd.Next(),
                Field3 = rnd.Next(),
                Field4 = rnd.Next(),
                Field5 = rnd.Next(),
                Field6 = rnd.Next(),
                Field7 = rnd.Next(),
                Field8 = rnd.Next(),
            };
            if (set.Add(item))
                i++;
        }
        return set;
    }

    // Helper method to get the value of the specified field.
    public static int GetFieldValue(TestStructure item, int fieldIndex)
    {
        return fieldIndex switch
        {
            0 => item.Field1,
            1 => item.Field2,
            2 => item.Field3,
            3 => item.Field4,
            4 => item.Field5,
            5 => item.Field6,
            6 => item.Field7,
            7 => item.Field8,
            _ => 0
        };
    }

    //==========================================================================
    // Variant 1: Dynamic insertion using List<T> (with BinarySearch + Insert)
    [Benchmark]
    public List<TestStructure> DynamicFill_List()
    {
        var baseline = BaseList;
        var result = new List<TestStructure>(baseline.Count);
        foreach (var item in baseline)
        {
            int index = result.BinarySearch(item, DynamicComparer);
            if (index < 0)
                index = ~index;
            result.Insert(index, item);
        }
        return result;
    }

    //==========================================================================
    // Variant 2: Dynamic insertion using SortedArray (custom implementation)
    [Benchmark]
    public SortedArray<TestStructure> DynamicFill_SortedArray()
    {
        var baseline = BaseList;
        var sortedArray = new SortedArray<TestStructure>(baseline.Count, DynamicComparer);
        foreach (var item in baseline)
        {
            sortedArray.Add(item);
        }
        return sortedArray;
    }

    //==========================================================================
    // Variant 3: Dynamic insertion using SortedDictionary.
    // The key is the element itself; uniqueness is ensured by the comparer.
    [Benchmark]
    public SortedDictionary<TestStructure, int> DynamicFill_SortedDictionary()
    {
        var baseline = BaseList;
        var sd = new SortedDictionary<TestStructure, int>(DynamicComparer);
        foreach (var item in baseline)
        {
            sd.Add(item, 0);
        }
        return sd;
    }

    //==========================================================================
    // Variant 4: Fill a SortedDictionary and then copy its keys into a List<T>.
    [Benchmark]
    public List<TestStructure> DynamicFill_SortedDictionaryToList()
    {
        var baseline = BaseList;
        var sd = new SortedDictionary<TestStructure, int>(DynamicComparer);
        foreach (var item in baseline)
        {
            sd.Add(item, 0);
        }
        return sd.Keys.ToList();
    }
    
    //==========================================================================
    // Variant 5: Fill a SortedList.
    [Benchmark]
    public List<TestStructure> DynamicFill_SortedList()
    {
        var baseline = BaseList;
        var sl = new SortedList<TestStructure, int>(DynamicComparer);
        foreach (var item in baseline)
        {
            sl.Add(item, 0);
        }
        return sl.Keys.ToList();
    }
}