Bounds on Complexity when Sorting Reals

0531334 - ÚI 2021 RIV US eng J - Journal Article
Jiřina, Marcel
Bounds on Complexity when Sorting Reals.
International Journal of Circuits, Systems and Signal Processing. Roč. 14, July (2020), s. 276-281. ISSN 1998-4464
R&D Projects: GA MŠMT LM2015068
Institutional support: RVO:67985807
Keywords : Linear time * Sorting reals * Time complexity
OECD category: Statistics and probability
Method of publishing: Open access

We derive the upper bounds on the complexity of the counting sort algorithm applied to reals. We show that the algorithm has a time complexity O(n) for n data items distributed uniformly or exponentially. The proof is based on the fact that the use of comparison-type sorting for small portion of a given data set is bounded by a linear function of n. Some numerical demonstrations are discussed.
Permanent Link: http://hdl.handle.net/11104/0310011