Customary Behavior of Sorting Reals with Linear Time Complexity

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.

I. Introduction

The purpose of this work is to present a modification of the counting sort [2] for reals as sorting keys. It may happen that several samples sorted fall into one cell (bucket). These samples form a group of unsorted samples. We propose to sort them by using a comparison sort, e.g. bubble sort or quicksort [4] , [6] . We show here that the number of samples falling into one bucket is very small not exceeding several tens in practice. At the same time, the number of buckets with such multiplicities is also limited. Based on upper estimations of multiplicities and their probabilities, we show the linear time complexity of the algorithm.