Awesome

Intro

This document describes a stable bottom-up adaptive merge sort named twinsort.

The primary goal is to provide a simplified alternative to quadsort.

The algorithm is about 150 lines of sparse C code that should be relatively easy to understand and port.

Twin swap

The twin_swap function is a pre-sorting routine which turns the array into sorted blocks of 2 elements. 8 9 4 1 2 3 6 0 5 7 becomes 8 9 1 4 2 3 0 6 5 7.

The twin swap routine also contains a reverse order run detector, so 6 5 4 3 2 1 is sorted into 1 2 3 4 5 6 rather than 5 6 3 4 1 2.

The swap and the run detection are carried out simultaneously, subsequently the reverse run detector has very little overhead.

Tail sort

The tail_sort function is a bottom-up merge sort which uses at most n / 2 swap memory.

It merges by copying the right block to swap memory and merging the tails of each block. The routine skips unnecessary merge operations and boundary checks.

The tail merge routine also contains a forward run detector with minimal overhead.

Performance

Overall twinsort is slightly faster than Timsort, most notably on random data.

Big O

Twinsort makes n comparisons when the data is already sorted or reverse sorted.

Data types

Twinsort only supports integers, this to keep things simple.

Visualization

In the visualization below eight sorts are performed on various distributions. These distributions are: Random, Ascending, Ascending Saw, Generic, Descending, Descending Saw, Random Tail, and Wave order.

The upper half shows the swap memory and the bottom half shows the main memory. Colors are used to differentiate between skip, swap, and merge operations.

Benchmarks

The following benchmark is based on the wolfsort benchmark on WSL gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1).

The source code was compiled using g++ -O3 -w -fpermissive bench.c. Each test was ran 100 times and both the best and average run time is reported. stablesort is c++'s std::stablesort.