Original title: Nearly All Reals Can Be Sorted with Linear Time Complexity
Authors: Jiřina, Marcel
Document type: Research reports
Year: 2021
Language: eng
Series: Technical Report, volume: V-1285
Abstract: We propose a variant of the counting sort modified for sorting reals in a linear time. It is assumed that the sorting key and pointers to the items being sorted are moved and individual items remain at the same place in the memory (in place sorting). In this case, the space complexity of the new variant of the algorithm is the same as the complexity of the quicksort. We also quantify the practical limits for possible sorting reals in a linear time. This possibility is assured under additional assumptions on the distribution of the sorting key, mainly the independence and identity of the distribution. Here we give a more general criteria easily applicable in practice. We also show that the algorithm is applicable for data that do not fulfill criteria for linear time complexity but even that the computation is faster than the system quicksort. A new, faster version of the algorithm is attached.
Keywords: algorithm; linear complexity; real sorting key; sorting; time complexity
Project no.: LM2015068 (CEP)
Funding provider: GA MŠk

Institution: Institute of Computer Science AS ČR (web)
Document availability information: Fulltext is available in the digital repository of the Academy of Sciences.
Original record: http://hdl.handle.net/11104/0321594

Permalink: http://www.nusl.cz/ntk/nusl-449084


The record appears in these collections:
Research > Institutes ASCR > Institute of Computer Science
Reports > Research reports