JesseSort2 is an in-place O(n) approximate sorting algorithm. It zips subarray pairs using only middle-index comparisons to determine zip order. Subarray sizes increase each pass. We show the value of preprocessing and introduce a few variations below.
Best Average Worst Memory Stable Deterministic
n-logn n-logn/2 n-1 n No Yes
JesseSort2 on 1024 values performs exactly 1023 comparisons (n-1). With 2^n input values, there is no overhead. Below are outputs from using right middle indices vs left middle indices.
JesseSort2 on 1023 values performs exactly 1013 value comparisons (n-logn). With 1025 values, there are 1023 comparisons. In both cases, some overhead is introduced to blindly merge values from subarrays with unequal lengths.
The most comparisons performed by JesseSort2 occur in the first few passes, when subarray sizes are small (1, 2, 4, etc). By changing the order of some of these early comparisons, or by fully sorting small subarrays, we can greatly reduce the number of false assumptions in the following passes. Adding additional accuracy early offers huge returns in performance, as this algorithm is built on compounding assumptions. We found the subarray lengths 4 and 8 to be a "sweet spot" for injecting preprocessing, as JesseSort2 already requires 3 or 7 comparisons to get to these points. After a preprocessing step, JesseSort2 can start from this larger subarray size pass and run to completion.
We explored other shortcuts. Below we describe a few patterns that have been explored. We use the naming convention:
- C## - Compare the values at these two indices and sort them (swap if needed).
- B## - Blindly swap the values at these two indices. This was inspired by Monty Hall and these are usually conditional on whether a prior step caused a swap. If the two values compared in a prior step did not swap, then a different (or no) blind swap may be more beneficial.
- R - Permute over all possible inputs and reorder (sort) values based on the average values at each index after following all prior steps. Note this only has to happen once to find and store the mapping function at this step.
- JS2# - JesseSort2 picks up with this new starting subarray size.
With only 3 comparisons, arrays of length 4 will only be sorted 33% of the time. However, they only need 4 comparisons to be sorted 67% of the time or 5 comparisons to be sorted 100% of the time. There are some variations of 1 and 2 comparisons that have neat results too.
TODO
Many creative shortcuts can be made when arrays reach length 8.
TODO
We could perform 1 additional middle index comparison to zip both halves again. Note that the last step already merges halves by default, so this just repeats that last step. The result is not as visually impressive.
We could use binary search to find better "middle" indices for merging, turning this into a O(logn) algorithm. This usually creates an offset, so only a section of subarray A and B are actually zipped. The remaining values from each are simply appended to each end. JesseSort2 is an approximate algorithm at heart, so while this binary search step variation can sometimes help a lot, it can also cause even more problems by shifting "middles" too far due to incorrect information. There is a lot of variance in these results, but we show both good and bad examples below.
We could add more than 1 comparison per subarray. If we expanded this to 2 or 3 or more comparisons, we have to space these anchors out carefully to avoid unbalanced Voronoi-style segments at the front/rear ends. With 2 comparisons, one's instinct might be to place anchors at the 33% and 67% index locations. But these would still act on the bottom 50% and top 50% of values, so these would essentially using suboptimal (non-middle) indices to decide zip order for each half. Using the indices at 25% and 75% locations to be the center points responsible for their equal-sized halves was theoretically more optimal. Results from some of these are below.
Rather than always use the exact middle index, one might care more about improving one end of the output array. So we looked into offsetting this index using a divisor, pushing this middle index further towards one end or the other. Some interesting results.
We tested injecting Insertion Sort (and others) at different stages of JesseSort2. It was relatively inexpensive to do these full sorts early on. Similar to the effect of preprocessing, these greatly smoothed/improved the end results. Inserting these full sorts every X steps was particularly useful for mitigating outliers (lowered variance) and cheaper than waiting until the very end.
TODO
TODO
I still haven't finished optimizing the merge phase of JesseSort, but I've been wanting to share this new sorting algorithm for almost a year now. Originally, I was going to name this one after my wife. When I told her it was only an approximate sorting algorithm though, she got offended and refused. 😂
I actually started working on this algorithm before the JesseSort one, but it looked a lot different back then. The idea came when I was visualizing Mergesort passes. I noticed that most of the subarrays looked like they already spanned the full input range a few iterations prior to completion. I wondered if I could save time by stopping Mergesort early, blindly zip these subarrays together (np.reshape(arr, (num_subarrays, subarray_size)).T.ravel()), and finish off with one ~O(n) Insertion Sort pass.
This kinda worked...but the Insertion Sort phase was still too slow and I wanted to improve it. I looked into reordering/sorting the subarrays somehow before the zip. The idea evolved into making limited comparisons to efficiently merge these subarrays, which, taken to the extreme, led to the single middle-index comparison idea.