Performance Comparison of three Sorting Algorithms Using Shared Data and Concurrency Mechanisms in Java

1*Abbas M. Rabiu, 2Etemi J. Garba, 3Benson Y. Baha, 2Yusuf M. Malgwi and 1Mu’azu Dauda

1Department of Computer Science, Federal University Dutse, Nigeria
2Department of Computer Science, Modibbo Adama University of Technology Yola, Nigeria
3Department of Information Technology, Modibbo Adama University of Technology, Yola, Nigeria

*Corresponding Author: mambas86@fud.edu.ng


ABSTRACT

Sorting large data sets or database is a problem commonly found in Computer Science and to find a solution to this problem, several quicksorting algorithms were developed while some need to be improved upon to make them more efficient. Sorting algorithms can be developed using both shared and non-shared data based on programmers’ choices. This paper aimed to develop three distinct sorting algorithms that involved shared data using three concurrency mechanisms in Java to measure their running times and to compare their performances. The main method used is the practical measurement of running times using benchmarking carried out on a machine with eight (8) processing cores. System current Time Millis () was used to measure time during the experiment. The results show that SD-Parallel quick sort implementation using Atomicity outperforms the other two algorithms. It was also shown that creating more threads leads to overhead when algorithms are developed using shared data. It was concluded that the running times of algorithms that involved shared data increase with the increase in the array size when proper synchronization is performed It was further revealed that SD-Parallel quick sort implemented using Acyclic-Barrier emerged as the second-best algorithm. Other concurrency mechanisms namely: Phaser, and Double-Atomicity provided by other Java JDK versions have the capacity of building more efficient framework that can be used to improve the performance of these algorithms due to their dynamic functionality. These and other concurrency mechanism provided by Java deserves further investigation as they are also capable of building more efficient algorithm.

Keyword: Algorithms, Atomicity, Running time, Performance, Sorting