Hi all, I was working independently on a sorting algorithm I call "BusSort" which is: - histogram based - cache aware - naturally stable mainly designed for the randomly distributed and duplication heavy data.
As designed, it outperforms TimSort and Dual-Pivot QuickSort on the randomly distributed and duplication-heavy data. It is a histogram-based bucketing sorting algorithm, which processes the data in chunks that are nearly L1-cache-sized buffer or bus and this is the core idea behind this algorithm. Instead of randomly writing the elements into their desired bucket over the full range, it writes them into the buffer and because the buffer mostly fits in the L1 cache, all the random writes become cache hits. After the buffer gets full, it flushes all the elements from each bucket into the main output array and it's more reliable than writing a single element as we are writing multiple elements at once. This phenomenon is the same as dropping the multiple passengers to their desired destination at once rather than one at a time, hence I call it "BusSort". This process is done from left to right so the stability is preserved. It recursively processes each bucket till the threshold and then uses Insertion Sort for the small-sized buckets. I have implemented this idea for both generic and int type to compare its speed against the faster non-stable sorting algorithms like DPQ. I have benchmarked it for multiple types of data, Ex. random, nearly sorted, duplication-heavy, etc with both positive and negative ranges. Below are the overall numbers I am getting. Benchmarked with JMH (5 warmup / 10 measurement iterations, 3 forks) on one consistent machine (i5-1035G1, Java 21): int[] vs Arrays.sort (Dual-Pivot Quicksort), n=100,000,000: - Random: 2.66x faster - Duplicates: 2.75x faster - Few duplicates: 1.95x faster - Clustered: 1.43x faster - Nearly sorted: 1.14x faster - Reverse sorted: 0.33x (3x slower - see limitations below) Generic T[] variant (via a ToIntFunction<T> key extractor) vs Arrays.sort (TimSort), n=10,000,000, sorting real keyed objects rather than boxed Integers: - Random: 2.87x faster - Few duplicates: 2.10x faster - Clustered: 1.68x faster - Duplicates: 1.64x faster - Reverse sorted: 0.56x, Nearly sorted: 0.53x (both slower - see limitations below) Advantages: - Naturally stable, no need for extra work - Faster, as it takes advantage of cache hits and bucket-based sorting together Limitations: - Extra Space, as it's a bucket based sorting algorithm it takes extra space roughly equal to the input size, plus some constant overhead for the histogram-related work. (As I have measured the memory usage, the generic version takes almost equal amount of memory as compared to TimSort) Adversarial case: - If the input contains multiple outliers at each recursion level then it will end up less fast. Solution for Adversarial case: - A fallback mechanism can be added, where after each histogram buildup the element count for each bucket can be checked and if it's beyond the expected one we can simply hand over the work to the other sorts. The full benchmark matrix and the other aspects like GC pressure numbers, peak-memory measurements, and the tuning methodology (sequential JMH sweep over bucket count, chunk size, and insertion-sort threshold) are available in the link below: https://github.com/dev-shreyaspatil/BusSort The step-by-step working of the algorithm using the small example is also available in the post with the link below: https://dev.to/dev-shreyas/i-built-a-stable-sorting-algorithm-that-beats-javas-dual-pivot-quicksort-fck My aim was to design a sorting algorithm which should be stable, fast, efficient and can scale with the data size. I have tried my best using the knowledge I can get and also tried to find the boundaries of this algorithm. Any suggestions on this from the experts who have deeper knowledge in this area are most welcome and I am curious about this algorithm whether it can perform well in any domain. Thanks for reading, Shreyas Patil https://www.linkedin.com/in/shreyaspatil14/
