Customary Behavior of Sorting Reals with Linear Time Complexity
Marcel Jiřina · 2020
Sorting with real number keys has time complexity n log n. This holds under the assumption that for all n samples a comparison sort is used. Here we propose to use the counting sort with just n cells for initial placement of samples. We resolve cases of groups of several samples placed into one cell by a comparison sort. Surprisingly, even this part has time complexity proportional to n. Numerical experiments confirm this finding and shows influence of the computing environment such as paging, and reflects a higher speed than the quicksort.