StateSort — Fastest Comparison Sort?

Author(s):

Originally published on Towards AI.

GET SORTED

Publishing this article for my friend John Oberschelp, so when you see “I,” it is John. Contact John at john@oberschelp.net about StateSort and other minitue.

StateSort is a stable comparison sort I developed that is faster than any comparison sort I have found — faster than Windows, Linux, and boost::range versions of sort and stable_sort. Check it out and let me know what you think…and if you know of a faster sort.

TLDR

1. Overview: A stable hybrid comparison-based sorting algorithm designed to outperform existing comparison sorts used in Windows, Linux, and Boost libraries.
2. Algorithm Mechanics: Combines Insertion Sort to create initial runs of up to 30 elements, followed by a simultaneous multiway merging algorithm for efficient merging.
3. Performance Metrics: Offers an O(n log(n)) time complexity and O(n) space complexity, making it efficient for large datasets.
4. Adaptability: Performs well on non-adaptive data but lacks adaptability compared to algorithms like TimSort.
5. Future Optimization: Shows promise for further improvement by enhancing buffer allocation efficiency.

Sorting algorithms are the backbone of efficient data management, enabling us to organize and analyze vast amounts of information quickly and accurately. StateSort is a new stable hybrid comparison-based sorting algorithm, boasting an impressive O(n log(n)) time complexity and O(n) space complexity. StateSort combines the efficiency of multiway merging with the simplicity of Insertion Sort to create initial runs, making it a compelling alternative to existing comparison sorts like Merge Sort and TimSort. In this article, we’ll explore how StateSort works, its performance on real-world data, and what makes it stand out versus other sorting algorithms.

You can test it yourself easily under Windows or Linux with just the race.sh or race.bat script, the sub-100 line race.cpp, and StateSort.h all provided in the github StateSort folder. Or send a sort to me, and I will compare it.

How it works

StateSort is a stable hybrid comparison-based sorting algorithm with O(n log(n)) time complexity and O(n) space complexity.

Like some modern hybrid sorts, StateSort starts by using InsertionSort to create initial runs of up to 30 elements. It then uses a simultaneous multiway merging algorithm to repeatedly combine multiple runs into larger runs until all elements are sorted. In the presented version, four runs are merged simultaneously. Before merging, the sorted order of all runs by their first element is determined, and this is the merged state. This state is maintained during the merge.

In this implementation, each state can be found after a label; so, for example, if the first elements of the runs A through D were ordered C <= D < B < A, the code to handle that state would follow the label “CDBA:.” Each and every state has its own label, which, in the case of a 4-way merge, requires 24 labels. At a state, the least element is appended to a buffer, the run is tested for exhaustion, and if not, the new next element is compared to determine the new state.

Once each run is exhausted, another unique state is entered, for example “BDC:”, then “CD:”, then “C:”.

Performance on real-world data

Unlike TimSort and others, this version of StateSort is not adaptive and is not designed to perform better on “real world” data. But it seems to do relatively well, as is, against other non-adaptive sorts. An earlier version produced this data:

Testing hardware

The software was tested on a Windows 10 Pro Version 22H2 PC with a Ryzen 3400G CPU and 16 GB RAM.

Testing software

Some of the software I used to test speed, stability, generate the graphs, etc., is provided in the Tests directory for your review. The IDE is Visual Studio 2022. As can be seen in the test code, efforts were made to compensate for the granularity of timers and operating system interrupts.

Observations

Stability

Obviously, the stability restriction can be removed to make a faster version. In my limited testing so far, this did not make a huge difference.

Adaptive Performance

I have made a few adaptive versions, all of which are much faster when natural sorted runs and reverse runs are found but are at least somewhat slower on random data. More work is needed.

Buffer Allocation

During testing, I noticed that allocating the buffer was sometimes a surprisingly substantial performance hit all by itself. This was possibly caused by the OS not wanting to allocate uninitialized buffers (seeing this as a security risk) and, therefore, initializing buffers to zeros, although I did not investigate this. To address this avoidable delay, I allow the caller to provide their own size N buffer, which I call a loaner buffer. The loaner buffer speedup was not used during any testing shown here.

Small Sorts

So far, I have ignored the speed of StateSort for small ( say less than 1000 elements ) sorts. Something can be put in place if StateSort performs poorly on these. As an example, some other modern sorts just defer to std::stable_sort.

Conclusion

StateSort represents a significant advancement in sorting technology, offering a stable and efficient solution with a time complexity of O(n log(n)) and space complexity of O(n). By leveraging Insertion Sort for initial runs and a simultaneous multiway merging algorithm, StateSort achieves impressive performance on various datasets. While it may not be adaptive like TimSort, its non-adaptive version still holds its own against other non-adaptive sorts. With its potential for further optimization and adaptability, StateSort is an exciting development in the field of sorting algorithms, providing developers with a powerful tool for managing and organizing data efficiently.

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI