u/booker388

Repo here: https://github.com/lewj85/jessesort

tl;dr Jessesort is up to 20% faster than std::sort on random inputs and up to 95% faster on structured inputs

Jessesort has two phases: insertion and merging. The insertion phase routes inputs to two games of Patience (similar to Solitaire). One game has ascending piles and the other has descending piles. Routes inputs to the optimal game based on current run direction. Make base array copies for pile tails to speed up binary search. Faster merge logic than the old Patience sort k-way.

Jessesort was already faster on structured inputs, but the new optimization changes finally pushed this past the goal of being faster on random inputs too. Added seven variations of the algorithm. The fastest on random input is V2 that simulates both Patience games and uses a blueprint to track ascending vs descending game and pile index in that game. It's up to 20% faster on random inputs and up to 95% faster on structured inputs.

Key changes introduced were: early input probing to route random-like and structured data into better insertion paths, removal of pile hints where direct bit-walk search proved faster, simulated pile layouts that reduce allocation and bookkeeping overhead, adaptive merge routing based on the structure produced during insertion, branchless merging with a tuned four-way unroll, reconstruction optimizations that simplify blueprint decoding and cursor updates, pointer-based merge kernels that substantially reduced hot-loop overhead, selective early freezing/overflow strategies in later variations, preservation of fast monotonic/structured-input exits, and targeted SIMD experiments that use fixed-width AVX2 comparisons where the pile shape makes them worthwhile.

Jessesort simulates dual patience games, flattens, and merges. Everything but the final merging is shown in the video.

https://github.com/lewj85/jessesort