u/ggende

Hello, I've created a sorting algorithm in C# that is:

• Stable
• O(n log n) average and worst case
• More performant than OrderBy() is almost all cases (sometimes quite substantially)
• More performant that Array.Sort() in most cases where the data is at least somewhat sorted, and typically within about 20% when sorting mid to large-sized random data sets
• A merge sort variant that uses a buffered reverse merge for the merging process and insertion sort to process small sub-arrays
• Uses a (as far as I can tell) novel approach to detecting and optimizing for data that is already sorted

I created this just as a personal challenge, so if even one person finds it useful, I'll consider that a success! :)

It's published it on both Github and NuGet, and I've posted full details on the algorithm with tons of benchmarks on my blog. I welcome any feedback or suggestions.

Here are a few benchmark highlights:

1,000,000 Sequential Integers:
YamSort   |   .66 ms
ArraySort |  4.79 ms
OrderBy   | 11.62 ms

1,000,000 Random Integers:
YamSort   | 58.08 ms
ArraySort | 47.24 ms
OrderBy   | 75.97 ms

1,000,000 Near-Sequential Integers:
YamSort   | 13.73 ms
ArraySort | 20.62 ms
OrderBy   | 40.03 ms

Real-World Windows Log File With 109,546 Lines:
YamSort   | 38.63 ms
ArraySort | 66.98 ms
OrderBy   | 59.79 ms

No AI was used in typing any of this post or in typing any of my blog post. AI assistance was used for some parts of the algorithm, as noted in the Acknowledgements portion of my blog post.

Edit: Fixed markdown formatting