Throwing my yams into the ring!
A few weeks ago I decided to try my hand at building my own sorting algorithm. I believe I’ve come up with something useful with a novel trick for adapting to the input data. I’ve decided to call the algorithm YamSort after my wife’s favorite snack food.1
YamSort is a stable sorting algorithm with optimizations for sorted and semi-sorted data, and it works with all comparable data types.
Specifically for the version I’ve created in C#, it works with all types that implement IComparable<T>. It is compatible with .NET Standard 2.1 (with some features only available in .NET 6+). It has a competitive performance profile with the unstable built-in Array.Sort() while being faster than the stable LINQ OrderBy() method in almost all situations.
Performance Analysis
Time Complexity
- O(n) – Best case (when data is already sorted)
- O(n log n) – Average and worst case
Memory Complexity
- O(n) – Uses a single n/2-sized buffer
- GC Impact – C# implementation sources the buffer from
ArrayPoolresulting in a minimal amount of garbage collection pressure
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
There are a lot more benchmarks at the end of the post.
Usage
First, install the package from NuGet, or download YamSort.cs from GitHub and copy it into your project.
To use YamSort, import the YamSort namespace and call YamSorter.Sort() on your target array or list. Sorting List<T> requires .NET 6.0 and higher. A separate YamSorter.SortReturning() method is available to return a new sorted collection without modifying the original.
Example:
using YamSort;
public class YamSortDemo
{
public void ExecuteYamSort()
{
int[] inputArray = [4, 1, 3, 2];
YamSorter.Sort(inputArray);
// inputArray now equals [1, 2, 3, 4]
List<int> inputList = [4, 1, 3, 2];
YamSorter.Sort(inputList);
// inputList now equals [1, 2, 3, 4]
}
public void ExecuteYamSortReturning()
{
int[] referenceArray = [4, 1, 3, 2];
int[] newArray = YamSorter.SortReturning(referenceArray);
// referenceArray still equals [4, 1, 3, 2]
// newArray equals [1, 2, 3, 4]
}
}Algorithm Details
YamSort is a hybrid merge sort that uses a buffered reverse merge2 when merging blocks together and insertion sort to quickly sort small blocks. While the use of reverse merge doesn’t seem to be particularly common, so far, none of this is new.
The part of YamSort that is (as far as I can find) novel, is that there is a check at the halfway point to see how much of the buffer is being used. This data can be used to accurately measure how sorted the two blocks were in the original array.
If the buffer is empty (i.e. every value copied into the buffer went right back into the right side), the data was already sorted in ascending order. If the buffer is still full (i.e. every value from the left side was copied to the right side), that means the data was sorted in descending order. If the buffer is about half full, that is an indicator that the data was random.
YamSort looks for a buffer that is either less than 25% full or greater than 75% full and adjusts a “sequence score” accordingly.
A higher sequence score indicates that the data is typically sorted and increases the threshold for using insertion sort to process small sub-arrays (since insertion sort is very fast on sorted arrays). If the sequence score reaches its maximum value, the reverse merge will enter a galloping mode where it uses a binary search to determine how many values should be moved and then moves them all in a single copy.
As the name implies, galloping mode is adapted from TimSort galloping. YamSort also use a threshold of repeated wins by a particular side before engaging the binary search. However, since galloping mode is only possible when there are strong indicators that the data is sorted, YamSort only needs 5 wins in a row to start a binary search (compared to 7 for TimSort).
When the sequence score is low, the data is mostly sorted in descending order. In this case, the threshold for using insertion sort is reduced (reverse sorted is a worst case scenario for insertion sort and takes O(n2) time). Galloping mode is also used at the minimum sequence score.
The result is an algorithm that is able to take advantage of data that is already sorted or close to being sorted while still keeping a simple highly efficient loop to iterate through random data as quickly as possible.
Potential Future Improvements
- Parallelization: As a merge sort, YamSort would be fairly easy to parallelize for major performance gains. A few quick attempts confirmed this is viable, but I didn’t make anything appropriate for release.
- Block Partitioning: YamSort focuses on improving the merging process. Other merge sort variants (e.g. TimSort, PowerSort) focus on how to best divide up the blocks to be merged. A naive attempt to tack PowerSort onto the front of YamSort resulted in a significant performance degradation, but there may be some combination that would improve performance.
- Duplicate Handling: YamSort’s optmizations are weakest when sorting data with a very large number of repeated values (see binary data benchmarks below). It may be possible to improve this with a separate heuristic that tracks repeated values.
Acknowledgements
Most of the code in YamSort was written by me, but there are a few exceptions.
The insertion sort and binary search algorithms were created by the AI at google.com/ai. I also used AI to help me find opportunities for performance improvements.
The optimized GreaterThan(), LessThan(), and LessThanOrEqual() methods were adapted from code found in ArraySortHelper.cs from the .NET source code. The MoveNansToFront() code came from there as well
Benchmarks
The benchmarks below use nine different data layouts. The code used to generate the data is available in the fuzzing tests on GitHub. All string data is originally generated as integers and then converted to strings.
The data layout types are as follows:
- Binary – Random assignment of 0s and 1s
- CleanPipeOrgan – Alternating ascending and descending sequential data
- ClusteredRandom – Random data using a normal distribution (bell curve)
- Random – Each number from 1 to N, in random order
- ReverseSequential – Each number from 1 to N, in descending order
- SemiPipeOrgan – The same as cleanPipeOrgan, but with ~10% random noise
- SemiReverseSequential – Each number from 1 to N, in descending order, with ~10% random noise
- SemiSequential – Each number from 1 to N, in ascending order, with ~10% random noise
- Sequential – Each number from 1 to N, in ascending order
All benchmarks were run in Windows 11 using a 9800X3D CPU with 32GB RAM.
On to the benchmarks…
Integer Results:
| Method | DataLayout | N | Mean
| YamSort | binary | 100 | 306.0 ns
| ArraySort | binary | 100 | 196.3 ns
| OrderBy | binary | 100 | 692.9 ns
| YamSort | binary | 1000 | 4,204.5 ns
| ArraySort | binary | 1000 | 2,638.2 ns
| OrderBy | binary | 1000 | 9,153.4 ns
| YamSort | binary | 10000 | 58,135.0 ns
| ArraySort | binary | 10000 | 33,534.4 ns
| OrderBy | binary | 10000 | 267,335.8 ns
| YamSort | binary | 100000 | 1,119,737.6 ns
| ArraySort | binary | 100000 | 691,657.4 ns
| OrderBy | binary | 100000 | 4,358,813.1 ns
| YamSort | binary | 1000000 | 11,905,103.8 ns
| ArraySort | binary | 1000000 | 7,857,252.5 ns
| OrderBy | binary | 1000000 | 41,557,550.7 ns
| YamSort | cleanPipeOrgan | 100 | 405.2 ns
| ArraySort | cleanPipeOrgan | 100 | 243.7 ns
| OrderBy | cleanPipeOrgan | 100 | 732.1 ns
| YamSort | cleanPipeOrgan | 1000 | 5,345.7 ns
| ArraySort | cleanPipeOrgan | 1000 | 3,361.9 ns
| OrderBy | cleanPipeOrgan | 1000 | 10,777.6 ns
| YamSort | cleanPipeOrgan | 10000 | 44,203.5 ns
| ArraySort | cleanPipeOrgan | 10000 | 67,395.7 ns
| OrderBy | cleanPipeOrgan | 10000 | 329,378.1 ns
| YamSort | cleanPipeOrgan | 100000 | 454,104.6 ns
| ArraySort | cleanPipeOrgan | 100000 | 1,708,224.2 ns
| OrderBy | cleanPipeOrgan | 100000 | 4,631,796.4 ns
| YamSort | cleanPipeOrgan | 1000000 | 4,586,211.5 ns
| ArraySort | cleanPipeOrgan | 1000000 | 18,715,865.0 ns
| OrderBy | cleanPipeOrgan | 1000000 | 47,569,001.7 ns
| YamSort | clusteredRandom | 100 | 411.9 ns
| ArraySort | clusteredRandom | 100 | 288.6 ns
| OrderBy | clusteredRandom | 100 | 658.8 ns
| YamSort | clusteredRandom | 1000 | 6,774.4 ns
| ArraySort | clusteredRandom | 1000 | 3,159.7 ns
| OrderBy | clusteredRandom | 1000 | 8,558.9 ns
| YamSort | clusteredRandom | 10000 | 259,850.2 ns
| ArraySort | clusteredRandom | 10000 | 230,910.5 ns
| OrderBy | clusteredRandom | 10000 | 546,454.3 ns
| YamSort | clusteredRandom | 100000 | 4,101,436.4 ns
| ArraySort | clusteredRandom | 100000 | 3,176,812.8 ns
| OrderBy | clusteredRandom | 100000 | 7,449,499.9 ns
| YamSort | clusteredRandom | 1000000 | 51,416,485.4 ns
| ArraySort | clusteredRandom | 1000000 | 39,616,997.4 ns
| OrderBy | clusteredRandom | 1000000 | 88,463,538.9 ns
| YamSort | random | 100 | 421.6 ns
| ArraySort | random | 100 | 302.5 ns
| OrderBy | random | 100 | 666.3 ns
| YamSort | random | 1000 | 6,325.8 ns
| ArraySort | random | 1000 | 3,362.0 ns
| OrderBy | random | 1000 | 8,249.2 ns
| YamSort | random | 10000 | 324,205.8 ns
| ArraySort | random | 10000 | 290,909.5 ns
| OrderBy | random | 10000 | 419,429.9 ns
| YamSort | random | 100000 | 4,997,931.8 ns
| ArraySort | random | 100000 | 4,048,095.2 ns
| OrderBy | random | 100000 | 6,481,177.6 ns
| YamSort | random | 1000000 | 58,084,357.3 ns
| ArraySort | random | 1000000 | 47,242,106.1 ns
| OrderBy | random | 1000000 | 75,970,993.3 ns
| YamSort | reverseSequential | 100 | 465.2 ns
| ArraySort | reverseSequential | 100 | 258.1 ns
| OrderBy | reverseSequential | 100 | 568.0 ns
| YamSort | reverseSequential | 1000 | 2,859.1 ns
| ArraySort | reverseSequential | 1000 | 3,835.4 ns
| OrderBy | reverseSequential | 1000 | 9,569.4 ns
| YamSort | reverseSequential | 10000 | 28,587.0 ns
| ArraySort | reverseSequential | 10000 | 57,452.9 ns
| OrderBy | reverseSequential | 10000 | 126,406.0 ns
| YamSort | reverseSequential | 100000 | 323,373.4 ns
| ArraySort | reverseSequential | 100000 | 716,144.3 ns
| OrderBy | reverseSequential | 100000 | 1,915,750.6 ns
| YamSort | reverseSequential | 1000000 | 3,393,277.5 ns
| ArraySort | reverseSequential | 1000000 | 7,830,491.5 ns
| OrderBy | reverseSequential | 1000000 | 24,214,692.0 ns
| YamSort | semiPipeOrgan | 100 | 396.8 ns
| ArraySort | semiPipeOrgan | 100 | 261.8 ns
| OrderBy | semiPipeOrgan | 100 | 846.7 ns
| YamSort | semiPipeOrgan | 1000 | 6,426.3 ns
| ArraySort | semiPipeOrgan | 1000 | 3,424.0 ns
| OrderBy | semiPipeOrgan | 1000 | 10,627.9 ns
| YamSort | semiPipeOrgan | 10000 | 76,697.9 ns
| ArraySort | semiPipeOrgan | 10000 | 146,962.0 ns
| OrderBy | semiPipeOrgan | 10000 | 389,734.2 ns
| YamSort | semiPipeOrgan | 100000 | 1,575,533.6 ns
| ArraySort | semiPipeOrgan | 100000 | 2,254,077.0 ns
| OrderBy | semiPipeOrgan | 100000 | 5,131,132.8 ns
| YamSort | semiPipeOrgan | 1000000 | 17,299,576.8 ns
| ArraySort | semiPipeOrgan | 1000000 | 25,911,258.8 ns
| OrderBy | semiPipeOrgan | 1000000 | 53,450,227.4 ns
| YamSort | semiRevSequential | 100 | 639.9 ns
| ArraySort | semiRevSequential | 100 | 272.1 ns
| OrderBy | semiRevSequential | 100 | 549.8 ns
| YamSort | semiRevSequential | 1000 | 5,921.1 ns
| ArraySort | semiRevSequential | 1000 | 4,094.8 ns
| OrderBy | semiRevSequential | 1000 | 9,521.1 ns
| YamSort | semiRevSequential | 10000 | 67,808.0 ns
| ArraySort | semiRevSequential | 10000 | 66,977.3 ns
| OrderBy | semiRevSequential | 10000 | 176,908.6 ns
| YamSort | semiRevSequential | 100000 | 1,499,035.1 ns
| ArraySort | semiRevSequential | 100000 | 1,804,217.8 ns
| OrderBy | semiRevSequential | 100000 | 3,376,975.9 ns
| YamSort | semiRevSequential | 1000000 | 15,934,762.7 ns
| ArraySort | semiRevSequential | 1000000 | 19,875,694.1 ns
| OrderBy | semiRevSequential | 1000000 | 37,112,355.8 ns
| YamSort | semiSequential | 100 | 241.3 ns
| ArraySort | semiSequential | 100 | 222.4 ns
| OrderBy | semiSequential | 100 | 492.5 ns
| YamSort | semiSequential | 1000 | 3,769.4 ns
| ArraySort | semiSequential | 1000 | 3,252.5 ns
| OrderBy | semiSequential | 1000 | 8,320.6 ns
| YamSort | semiSequential | 10000 | 43,228.5 ns
| ArraySort | semiSequential | 10000 | 57,973.4 ns
| OrderBy | semiSequential | 10000 | 187,288.9 ns
| YamSort | semiSequential | 100000 | 1,188,767.5 ns
| ArraySort | semiSequential | 100000 | 1,805,105.3 ns
| OrderBy | semiSequential | 100000 | 3,398,328.8 ns
| YamSort | semiSequential | 1000000 | 13,729,510.7 ns
| ArraySort | semiSequential | 1000000 | 20,617,283.3 ns
| OrderBy | semiSequential | 1000000 | 40,027,745.0 ns
| YamSort | sequential | 100 | 101.2 ns
| ArraySort | sequential | 100 | 192.5 ns
| OrderBy | sequential | 100 | 409.3 ns
| YamSort | sequential | 1000 | 540.8 ns
| ArraySort | sequential | 1000 | 2,389.6 ns
| OrderBy | sequential | 1000 | 5,446.7 ns
| YamSort | sequential | 10000 | 5,057.8 ns
| ArraySort | sequential | 10000 | 31,038.4 ns
| OrderBy | sequential | 10000 | 79,033.4 ns
| YamSort | sequential | 100000 | 106,890.4 ns
| ArraySort | sequential | 100000 | 447,893.2 ns
| OrderBy | sequential | 100000 | 1,225,887.5 ns
| YamSort | sequential | 1000000 | 663,420.8 ns
| ArraySort | sequential | 1000000 | 4,794,039.0 ns
| OrderBy | sequential | 1000000 | 11,621,401.4 ns
Double (Floating Point) Results:
| Method | DataLayout | N | Mean
| YamSort | binary | 100 | 332.2 ns
| ArraySort | binary | 100 | 242.4 ns
| OrderBy | binary | 100 | 848.5 ns
| YamSort | binary | 1000 | 5,208.0 ns
| ArraySort | binary | 1000 | 2,800.8 ns
| OrderBy | binary | 1000 | 11,933.3 ns
| YamSort | binary | 10000 | 72,281.6 ns
| ArraySort | binary | 10000 | 35,127.0 ns
| OrderBy | binary | 10000 | 319,958.1 ns
| YamSort | binary | 100000 | 1,518,674.5 ns
| ArraySort | binary | 100000 | 850,126.1 ns
| OrderBy | binary | 100000 | 5,106,625.5 ns
| YamSort | binary | 1000000 | 16,073,829.8 ns
| ArraySort | binary | 1000000 | 9,169,048.7 ns
| OrderBy | binary | 1000000 | 69,942,202.7 ns
| YamSort | cleanPipeOrgan | 100 | 423.6 ns
| ArraySort | cleanPipeOrgan | 100 | 278.3 ns
| OrderBy | cleanPipeOrgan | 100 | 904.3 ns
| YamSort | cleanPipeOrgan | 1000 | 5,438.5 ns
| ArraySort | cleanPipeOrgan | 1000 | 3,825.1 ns
| OrderBy | cleanPipeOrgan | 1000 | 12,372.0 ns
| YamSort | cleanPipeOrgan | 10000 | 54,280.2 ns
| ArraySort | cleanPipeOrgan | 10000 | 93,304.0 ns
| OrderBy | cleanPipeOrgan | 10000 | 406,442.4 ns
| YamSort | cleanPipeOrgan | 100000 | 559,233.0 ns
| ArraySort | cleanPipeOrgan | 100000 | 2,190,398.5 ns
| OrderBy | cleanPipeOrgan | 100000 | 6,702,955.3 ns
| YamSort | cleanPipeOrgan | 1000000 | 5,840,677.3 ns
| ArraySort | cleanPipeOrgan | 1000000 | 23,435,919.8 ns
| OrderBy | cleanPipeOrgan | 1000000 | 53,663,267.4 ns
| YamSort | clusteredRandom | 100 | 436.4 ns
| ArraySort | clusteredRandom | 100 | 322.3 ns
| OrderBy | clusteredRandom | 100 | 731.2 ns
| YamSort | clusteredRandom | 1000 | 6,783.7 ns
| ArraySort | clusteredRandom | 1000 | 4,052.7 ns
| OrderBy | clusteredRandom | 1000 | 8,961.3 ns
| YamSort | clusteredRandom | 10000 | 378,236.7 ns
| ArraySort | clusteredRandom | 10000 | 347,921.4 ns
| OrderBy | clusteredRandom | 10000 | 520,461.2 ns
| YamSort | clusteredRandom | 100000 | 5,648,510.2 ns
| ArraySort | clusteredRandom | 100000 | 4,807,911.1 ns
| OrderBy | clusteredRandom | 100000 | 7,514,081.6 ns
| YamSort | clusteredRandom | 1000000 | 68,255,817.0 ns
| ArraySort | clusteredRandom | 1000000 | 57,922,162.4 ns
| OrderBy | clusteredRandom | 1000000 | 87,793,531.1 ns
| YamSort | random | 100 | 493.2 ns
| ArraySort | random | 100 | 349.9 ns
| OrderBy | random | 100 | 750.0 ns
| YamSort | random | 1000 | 6,471.1 ns
| ArraySort | random | 1000 | 3,896.6 ns
| OrderBy | random | 1000 | 9,004.9 ns
| YamSort | random | 10000 | 379,800.9 ns
| ArraySort | random | 10000 | 390,964.9 ns
| OrderBy | random | 10000 | 521,704.0 ns
| YamSort | random | 100000 | 5,792,059.0 ns
| ArraySort | random | 100000 | 4,861,521.7 ns
| OrderBy | random | 100000 | 7,505,856.9 ns
| YamSort | random | 1000000 | 66,820,146.2 ns
| ArraySort | random | 1000000 | 56,886,914.3 ns
| OrderBy | random | 1000000 | 131,269,731.7 ns
| YamSort | reverseSequential | 100 | 517.5 ns
| ArraySort | reverseSequential | 100 | 294.2 ns
| OrderBy | reverseSequential | 100 | 634.1 ns
| YamSort | reverseSequential | 1000 | 3,419.9 ns
| ArraySort | reverseSequential | 1000 | 4,742.6 ns
| OrderBy | reverseSequential | 1000 | 9,576.7 ns
| YamSort | reverseSequential | 10000 | 33,704.4 ns
| ArraySort | reverseSequential | 10000 | 59,973.5 ns
| OrderBy | reverseSequential | 10000 | 136,366.0 ns
| YamSort | reverseSequential | 100000 | 401,358.2 ns
| ArraySort | reverseSequential | 100000 | 813,882.7 ns
| OrderBy | reverseSequential | 100000 | 1,984,669.0 ns
| YamSort | reverseSequential | 1000000 | 4,919,918.6 ns
| ArraySort | reverseSequential | 1000000 | 8,823,290.7 ns
| OrderBy | reverseSequential | 1000000 | 54,774,973.3 ns
| YamSort | semiPipeOrgan | 100 | 433.2 ns
| ArraySort | semiPipeOrgan | 100 | 296.2 ns
| OrderBy | semiPipeOrgan | 100 | 875.5 ns
| YamSort | semiPipeOrgan | 1000 | 7,017.2 ns
| ArraySort | semiPipeOrgan | 1000 | 3,948.3 ns
| OrderBy | semiPipeOrgan | 1000 | 11,554.6 ns
| YamSort | semiPipeOrgan | 10000 | 88,125.3 ns
| ArraySort | semiPipeOrgan | 10000 | 178,603.1 ns
| OrderBy | semiPipeOrgan | 10000 | 443,717.6 ns
| YamSort | semiPipeOrgan | 100000 | 2,045,145.2 ns
| ArraySort | semiPipeOrgan | 100000 | 2,777,496.8 ns
| OrderBy | semiPipeOrgan | 100000 | 5,749,938.6 ns
| YamSort | semiPipeOrgan | 1000000 | 19,843,321.2 ns
| ArraySort | semiPipeOrgan | 1000000 | 30,736,341.5 ns
| OrderBy | semiPipeOrgan | 1000000 | 61,421,386.1 ns
| YamSort | semiRevSequential | 100 | 673.0 ns
| ArraySort | semiRevSequential | 100 | 308.7 ns
| OrderBy | semiRevSequential | 100 | 629.2 ns
| YamSort | semiRevSequential | 1000 | 6,554.3 ns
| ArraySort | semiRevSequential | 1000 | 4,611.1 ns
| OrderBy | semiRevSequential | 1000 | 10,407.9 ns
| YamSort | semiRevSequential | 10000 | 82,284.8 ns
| ArraySort | semiRevSequential | 10000 | 83,746.9 ns
| OrderBy | semiRevSequential | 10000 | 197,965.1 ns
| YamSort | semiRevSequential | 100000 | 1,885,665.0 ns
| ArraySort | semiRevSequential | 100000 | 2,222,312.8 ns
| OrderBy | semiRevSequential | 100000 | 3,616,185.1 ns
| YamSort | semiRevSequential | 1000000 | 18,800,365.6 ns
| ArraySort | semiRevSequential | 1000000 | 24,024,922.5 ns
| OrderBy | semiRevSequential | 1000000 | 39,751,996.7 ns
| YamSort | semiSequential | 100 | 265.8 ns
| ArraySort | semiSequential | 100 | 250.9 ns
| OrderBy | semiSequential | 100 | 518.4 ns
| YamSort | semiSequential | 1000 | 4,233.4 ns
| ArraySort | semiSequential | 1000 | 3,744.6 ns
| OrderBy | semiSequential | 1000 | 8,559.4 ns
| YamSort | semiSequential | 10000 | 51,645.0 ns
| ArraySort | semiSequential | 10000 | 78,226.3 ns
| OrderBy | semiSequential | 10000 | 182,783.0 ns
| YamSort | semiSequential | 100000 | 1,551,401.7 ns
| ArraySort | semiSequential | 100000 | 2,170,103.2 ns
| OrderBy | semiSequential | 100000 | 3,612,535.3 ns
| YamSort | semiSequential | 1000000 | 16,458,584.1 ns
| ArraySort | semiSequential | 1000000 | 24,715,967.2 ns
| OrderBy | semiSequential | 1000000 | 40,600,545.1 ns
| YamSort | sequential | 100 | 132.5 ns
| ArraySort | sequential | 100 | 203.3 ns
| OrderBy | sequential | 100 | 467.8 ns
| YamSort | sequential | 1000 | 838.9 ns
| ArraySort | sequential | 1000 | 2,441.7 ns
| OrderBy | sequential | 1000 | 5,847.6 ns
| YamSort | sequential | 10000 | 8,053.4 ns
| ArraySort | sequential | 10000 | 35,667.2 ns
| OrderBy | sequential | 10000 | 76,580.1 ns
| YamSort | sequential | 100000 | 106,357.0 ns
| ArraySort | sequential | 100000 | 507,985.3 ns
| OrderBy | sequential | 100000 | 2,548,576.7 ns
| YamSort | sequential | 1000000 | 1,139,903.4 ns
| ArraySort | sequential | 1000000 | 5,117,002.2 ns
| OrderBy | sequential | 1000000 | 12,496,837.4 ns
String Results:
| Method | DataLayout | N | Mean
| YamSort | binary | 100 | 4.982 us
| ArraySort | binary | 100 | 3.080 us
| OrderBy | binary | 100 | 2.230 us
| YamSort | binary | 1000 | 68.817 us
| ArraySort | binary | 1000 | 40.927 us
| OrderBy | binary | 1000 | 35.187 us
| YamSort | binary | 10000 | 874.405 us
| ArraySort | binary | 10000 | 511.533 us
| OrderBy | binary | 10000 | 506.784 us
| YamSort | binary | 100000 | 8,454.605 us
| ArraySort | binary | 100000 | 6,170.508 us
| OrderBy | binary | 100000 | 7,971.566 us
| YamSort | binary | 1000000 | 80,356.373 us
| ArraySort | binary | 1000000 | 70,295.440 us
| OrderBy | binary | 1000000 | 80,616.748 us
| YamSort | cleanPipeOrgan | 100 | 7.958 us
| ArraySort | cleanPipeOrgan | 100 | 9.132 us
| OrderBy | cleanPipeOrgan | 100 | 7.947 us
| YamSort | cleanPipeOrgan | 1000 | 111.232 us
| ArraySort | cleanPipeOrgan | 1000 | 211.389 us
| OrderBy | cleanPipeOrgan | 1000 | 163.723 us
| YamSort | cleanPipeOrgan | 10000 | 1,176.438 us
| ArraySort | cleanPipeOrgan | 10000 | 3,483.968 us
| OrderBy | cleanPipeOrgan | 10000 | 2,828.860 us
| YamSort | cleanPipeOrgan | 100000 | 12,151.822 us
| ArraySort | cleanPipeOrgan | 100000 | 43,709.043 us
| OrderBy | cleanPipeOrgan | 100000 | 37,585.503 us
| YamSort | cleanPipeOrgan | 1000000 | 118,018.825 us
| ArraySort | cleanPipeOrgan | 1000000 | 523,077.560 us
| OrderBy | cleanPipeOrgan | 1000000 | 435,292.773 us
| YamSort | clusteredRandom | 100 | 12.045 us
| ArraySort | clusteredRandom | 100 | 13.447 us
| OrderBy | clusteredRandom | 100 | 10.374 us
| YamSort | clusteredRandom | 1000 | 219.197 us
| ArraySort | clusteredRandom | 1000 | 237.566 us
| OrderBy | clusteredRandom | 1000 | 211.553 us
| YamSort | clusteredRandom | 10000 | 3,020.525 us
| ArraySort | clusteredRandom | 10000 | 3,024.785 us
| OrderBy | clusteredRandom | 10000 | 2,821.043 us
| YamSort | clusteredRandom | 100000 | 42,783.658 us
| ArraySort | clusteredRandom | 100000 | 39,208.670 us
| OrderBy | clusteredRandom | 100000 | 37,777.820 us
| YamSort | clusteredRandom | 1000000 | 569,292.155 us
| ArraySort | clusteredRandom | 1000000 | 563,054.147 us
| OrderBy | clusteredRandom | 1000000 | 589,129.593 us
| YamSort | random | 100 | 10.941 us
| ArraySort | random | 100 | 16.151 us
| OrderBy | random | 100 | 12.117 us
| YamSort | random | 1000 | 213.517 us
| ArraySort | random | 1000 | 277.593 us
| OrderBy | random | 1000 | 218.802 us
| YamSort | random | 10000 | 3,323.035 us
| ArraySort | random | 10000 | 3,845.297 us
| OrderBy | random | 10000 | 3,228.699 us
| YamSort | random | 100000 | 47,121.986 us
| ArraySort | random | 100000 | 50,942.557 us
| OrderBy | random | 100000 | 45,732.128 us
| YamSort | random | 1000000 | 611,711.273 us
| ArraySort | random | 1000000 | 637,755.573 us
| OrderBy | random | 1000000 | 610,211.300 us
| YamSort | reverseSequential | 100 | 8.260 us
| ArraySort | reverseSequential | 100 | 12.426 us
| OrderBy | reverseSequential | 100 | 9.619 us
| YamSort | reverseSequential | 1000 | 64.349 us
| ArraySort | reverseSequential | 1000 | 227.615 us
| OrderBy | reverseSequential | 1000 | 175.882 us
| YamSort | reverseSequential | 10000 | 620.519 us
| ArraySort | reverseSequential | 10000 | 3,233.899 us
| OrderBy | reverseSequential | 10000 | 2,552.798 us
| YamSort | reverseSequential | 100000 | 6,700.616 us
| ArraySort | reverseSequential | 100000 | 41,668.327 us
| OrderBy | reverseSequential | 100000 | 34,055.957 us
| YamSort | reverseSequential | 1000000 | 61,783.975 us
| ArraySort | reverseSequential | 1000000 | 502,436.254 us
| OrderBy | reverseSequential | 1000000 | 406,804.467 us
| YamSort | semiPipeOrgan | 100 | 7.945 us
| ArraySort | semiPipeOrgan | 100 | 10.311 us
| OrderBy | semiPipeOrgan | 100 | 8.888 us
| YamSort | semiPipeOrgan | 1000 | 151.890 us
| ArraySort | semiPipeOrgan | 1000 | 212.868 us
| OrderBy | semiPipeOrgan | 1000 | 165.292 us
| YamSort | semiPipeOrgan | 10000 | 2,202.778 us
| ArraySort | semiPipeOrgan | 10000 | 3,527.220 us
| OrderBy | semiPipeOrgan | 10000 | 3,077.139 us
| YamSort | semiPipeOrgan | 100000 | 24,073.425 us
| ArraySort | semiPipeOrgan | 100000 | 47,788.368 us
| OrderBy | semiPipeOrgan | 100000 | 42,056.660 us
| YamSort | semiPipeOrgan | 1000000 | 251,988.904 us
| ArraySort | semiPipeOrgan | 1000000 | 549,471.307 us
| OrderBy | semiPipeOrgan | 1000000 | 484,366.147 us
| YamSort | semiRevSequential | 100 | 11.302 us
| ArraySort | semiRevSequential | 100 | 13.454 us
| OrderBy | semiRevSequential | 100 | 10.235 us
| YamSort | semiRevSequential | 1000 | 132.868 us
| ArraySort | semiRevSequential | 1000 | 251.783 us
| OrderBy | semiRevSequential | 1000 | 194.053 us
| YamSort | semiRevSequential | 10000 | 1,737.792 us
| ArraySort | semiRevSequential | 10000 | 3,481.142 us
| OrderBy | semiRevSequential | 10000 | 2,823.976 us
| YamSort | semiRevSequential | 100000 | 19,317.816 us
| ArraySort | semiRevSequential | 100000 | 44,755.508 us
| OrderBy | semiRevSequential | 100000 | 37,333.859 us
| YamSort | semiRevSequential | 1000000 | 202,776.662 us
| ArraySort | semiRevSequential | 1000000 | 532,344.362 us
| OrderBy | semiRevSequential | 1000000 | 447,593.136 us
| YamSort | semiSequential | 100 | 8.255 us
| ArraySort | semiSequential | 100 | 13.689 us
| OrderBy | semiSequential | 100 | 10.527 us
| YamSort | semiSequential | 1000 | 104.116 us
| ArraySort | semiSequential | 1000 | 237.506 us
| OrderBy | semiSequential | 1000 | 184.912 us
| YamSort | semiSequential | 10000 | 1,446.836 us
| ArraySort | semiSequential | 10000 | 3,454.293 us
| OrderBy | semiSequential | 10000 | 2,808.580 us
| YamSort | semiSequential | 100000 | 16,553.962 us
| ArraySort | semiSequential | 100000 | 44,434.623 us
| OrderBy | semiSequential | 100000 | 37,199.184 us
| YamSort | semiSequential | 1000000 | 175,861.924 us
| ArraySort | semiSequential | 1000000 | 538,733.329 us
| OrderBy | semiSequential | 1000000 | 449,419.187 us
| YamSort | sequential | 100 | 6.975 us
| ArraySort | sequential | 100 | 13.534 us
| OrderBy | sequential | 100 | 10.372 us
| YamSort | sequential | 1000 | 69.001 us
| ArraySort | sequential | 1000 | 228.243 us
| OrderBy | sequential | 1000 | 176.490 us
| YamSort | sequential | 10000 | 551.751 us
| ArraySort | sequential | 10000 | 3,234.612 us
| OrderBy | sequential | 10000 | 2,551.606 us
| YamSort | sequential | 100000 | 5,653.712 us
| ArraySort | sequential | 100000 | 41,445.056 us
| OrderBy | sequential | 100000 | 33,531.227 us
| YamSort | sequential | 1000000 | 54,925.383 us
| ArraySort | sequential | 1000000 | 503,933.092 us
| OrderBy | sequential | 1000000 | 405,102.529 us
Real-World String Results:
- LogStrings1 – 16.0MB log file with 109,546 lines
- LogStrings2 – 4.14MB log file with 14,662 lines; ~85% (est) of the lines are one of two common lines
- Neither log file contains timestamps (i.e. they are not already sorted)
| Method | DataLayout | N | Mean
| YamSort | logStrings1 | 100 | 38.63 ms
| ArraySort | logStrings1 | 100 | 66.98 ms
| OrderBy | logStrings1 | 100 | 59.79 ms
| YamSort | logStrings2 | 100 | 15.46 ms
| ArraySort | logStrings2 | 100 | 22.34 ms
| OrderBy | logStrings2 | 100 | 22.96 ms
- At least once a week, I slice up sweet potatoes that she roasts in the oven and keeps as a snack… but SweetPotatoSort doesn’t roll off the tongue quite the same (and us Americans don’t really know that sweet potatoes and yams technically aren’t the same thing☺). Also, it’s Yet Another Merge sort. ↩︎
- A buffered reverse merge copies the smaller of two pre-sorted blocks into a buffer and then fills in the remaining values from right to left by continuously comparing the highest value remaining in both the buffer and the half of the original array that was not copied to the buffer. In the case of YamSort, the size of the right side is always equal to or smaller than the left side. This frees the right side to be immediately overwritten.
Example:
Array = [2, 3, 7, 1, 4, 9]
Buffer = [_,_,_]
⇓
Array = [2, 3, 7,_,_,_]
Buffer = [1, 4, 9]
⇓
Array = [2, 3, 7,_,_, 9]
Buffer = [1, 4,_]
⇓
Array = [2, 3,_,_, 7, 9]
Buffer = [1, 4,_]
⇓
Array = [2, 3,_, 4, 7, 9]
Buffer = [1,_,_]
⇓
Array = [2,_, 3, 4, 7, 9]
Buffer = [1,_,_]
⇓
Array = [_, 2, 3, 4, 7, 9]
Buffer = [1,_,_]
⇓
Array = [1, 2, 3, 4, 7, 9]
Buffer = [_,_,_]
↩︎
Leave a Reply