Customary Behavior of Sorting Reals with Linear Time Complexity

0533287 - ÚI 2021 RIV US eng C - Conference Paper (international conference)
Jiřina, Marcel
Customary Behavior of Sorting Reals with Linear Time Complexity.
Proceedings of 2nd International Conference on Mathematics and Computers in Science and Engineering (MACISE 2020). Piscataway: IEEE, 2020, s. 268-271. ISBN 978-1-7281-6695-7.
[MACISE 2020: International Conference on Mathematics and Computers in Science and Engineering /2./. Madrid (ES), 18.01.2020-20.01.2020]
R&D Projects: GA MŠMT LM2015068
Institutional support: RVO:67985807
Keywords : sorting algorithm * sorting reals * linear time complexity * countingsort
OECD category: Computer hardware and architecture

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.
Permanent Link: http://hdl.handle.net/11104/0311712