Complexity analysis and performance of double hashing sort algorithm

Author

1 Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt

2 College of Computer Science and Engineering, Hail University, Hail, Kingdom of Saudi Arabi

https://doi.org/10.1186/s42787-019-0004-2

Abstract

Sorting an array of n elements represents one of the leading problems in different
fields of computer science such as databases, graphs, computational geometry, and
bioinformatics. A large number of sorting algorithms have been proposed based on
different strategies. Recently, a sequential algorithm, called double hashing sort
(DHS) algorithm, has been shown to exceed the quick sort algorithm in performance
by 10–25%. In this paper, we study this technique from the standpoints of
complexity analysis and the algorithm’s practical performance. We propose a new
complexity analysis for the DHS algorithm based on the relation between the size of
the input and the domain of the input elements. Our results reveal that the previous
complexity analysis was not accurate. We also show experimentally that the
counting sort algorithm performs significantly better than the DHS algorithm. Our
experimental studies are based on six benchmarks; the percentage of improvement
was roughly 46% on the average for all cases studied.

Keywords

Journal of the Egyptian Mathematical Society
Volume 27, Issue 1
2019
Pages 1-12

Files

Share

How to cite

Statistics