An $O(N)$ Sorting Algorithm: Machine Learning Sorting

Sorting, as a fundamental operation on data, has attracted intensively interest from the beginning of computing [1]. Lots of excellent algorithms have been designed, however, it's been proven that sorting algorithms based on comparison have a fundamental requirement of Ω(N log N) comparisons, which means O(N log N) time complexity. Recent years, with the emergence of big data (even terabytes of data), efficiency becomes more important for data processing, and researchers have put many efforts to make the sorting algorithms more efficient. Most of the state-of-art sorting algorithms employ parallel computing to handle big datasets and have accomplished outstanding achievements [2-6]. For example [7], in 2015, FuxiSort [8], developed by Alibaba Group, is a distributed sort implementation on top of Apsara. FuxiSort is able to complete the 100TB Daytona GraySort benchmark in 377 seconds on random non-skewed dataset and 510 seconds on skewed dataset, and Indy GraySort benchmark in 329 seconds.