Experimental adaptive sort - matches std::sort on random input, 2-8x faster on structured data

Hi all,

I’ve been developing an adaptive sorting algorithm, tentatively called **JesseSort**, which aims to exploit partial order in input data while still being competitive with standard library sorts on random input. I’m looking for feedback on design and potential adoption strategies.

# What it does

* Detects natural runs in the input (ascending, descending, or random) with a tiny lookahead.
* Maintains two sets of piles for ascending and descending runs, essentially a dual-patience sort.
* Falls back to tiny 8-value bitonic sort networks on detected random regions.
* When this random-input block is run too many times, it falls back to **std::sort**.
* Currently merges adjacent runs in a naive/bottom-up way.

# Current numbers

Median runtime ratios vs `std::sort` over 100 trials:

|Input Type|1k Values|10k|100k|1M|
|:-|:-|:-|:-|:-|
|Random|**0.984**|1.032|1.042|1.088|
|Sorted|1.022|**0.679**|**0.583**|1.448?|
|Reverse|1.636|1.076|**0.900**|2.101?|
|Sorted+Noise(5%)|1.048|1.041|1.079|1.201|
|Random+Repeats(50%)|1.037|1.032|1.031|1.089|
|Jitter|1.012|**0.674**|**0.586**|1.443?|
|Alternating|**0.829**|1.011|**0.974**|1.018|
|Sawtooth|1.121|**0.960**|**0.978**|1.072|
|BlockSorted|1.046|**0.950**|**0.928**|1.153|
|OrganPipe|**0.446**|**0.232**|**0.138**|**0.268**|
|Rotated|**0.596**|**0.522**|**0.396**|**0.716**|
|Signal|1.402|**0.828**|**0.659**|**0.582**|

**Notes:**

* Ratios are `JesseSort` / `std::sort`. **Values <1 indicate JesseSort is faster.** 0.5 means JesseSort takes half the time (2x faster). 2.0 means JesseSort takes twice as much time (2x slower).
* Large input blow-ups (`?`) appear to be outliers on my machine, but would be curious to see if others see the same pattern.

# Current issues / questions

1. **Handoff threshold:** Detecting random input too early loses semi-structured gains; too late slows random input. How should this balance be tuned?
2. **Fallback vs. std::sort:** Could JesseSort itself (dual patience games) serve as a better fallback than heap sort in standard introsort implementations?
3. **Merge optimizations:** Current merge is bottom-up adjacent. I’ve prototyped a TimSort-style merge that merges smaller runs first. Minor speedups in most cases but I haven't tested it enough.
4. **Memory layout & cache:** Some sensitivity to variable placement and data alignment is noticeable. Any advice for robust layout-sensitive optimizations?
5. **Real-world adoption:** Even if slightly slower on purely random input (\~5%), the structured input gains are often >50%. Would such an algorithm be worth promoting or considered niche? If the hit to random input is too significant, maybe this would find a better home as an alternative like `std::structured_sort`?

I’m looking for input on:

* Algorithmic improvements, especially for the random vs structured handoff
* Practical concerns for integration into standard libraries
* Benchmark methodology for mixed input distributions
* Real-world test datasets that might showcase advantages

Code and full details are available here: [https://github.com/lewj85/jessesort](https://github.com/lewj85/jessesort)

Thanks

https://redd.it/1r8n7vi
@r_cpp