Performance Analysis of a Faster In−place External Sorting Algorithm

Main Article Content

Asaduzzaman Nur Shuvo
Apurba Adhikary
Md. Bipul Hossain
Sultana Jahan Soheli

Abstract

Data sets in large applications are often too gigantic to fit completely inside the computer’s internal memory. The resulting input/output communication (or I/O) between fast internal memory and slower external memory (such as disks) can be a major performance bottle−neck. While applying sorting on this huge data set, it is essential to do external sorting. This paper is concerned with a new in−place external sorting algorithm. Our proposed algorithm uses the concept of Quick−Sort and Divide−and−Conquer approaches resulting in a faster sorting algorithm avoiding any additional disk space. In addition, we showed that the average time complexity can be reduced compared to the existing external sorting approaches.

Keywords:
External sorting, in−place sorting, sorting, external memory.

Article Details

How to Cite
Nur Shuvo, A., Adhikary, A., Hossain, M. B., & Jahan Soheli, S. (2020). Performance Analysis of a Faster In−place External Sorting Algorithm. Asian Journal of Research in Computer Science, 4(4), 1-7. https://doi.org/10.9734/ajrcos/2019/v4i430122
Section
Original Research Article

References

Knuth DE. The art of computer programming, sorting and searching, addition Wesley reading. MA. 1973;3.

Md. Nasim Adnan, Md. Islam, Md. Nur Islam, Md. Shohorab Hossen. A faster hybrid external sorting algorithm with no additional disk space. International Conference on Computer and Information Technology (ICCIT); 2002.

Fang−Cheng Leu, Yin−Te Tsai, Chuan Yi Tang. An efficient external sorting algorithm; 2000.

Dufrene WR, Lin FC. An efficient sorting algorithm with no additional space. Comput. J. 1992;35.

Singh B, Naps TL. Introduction to data structures. West publishing Co, St Paul, MN; 1985.

Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran. Fundamentals of computer algorithms. W. H. Freeman and Company; 1998.

Vitter JS, Shriver EAM. Algorithm for parallel memory, I: Two−level memories. Algorithmica. 1994;110−147.

Arge L, Vitter JS. Optimal dynamic interval management in external memory. In Proc. IEEE Symp. on Foundations of Comp. Sci; 1996.

Bayer R, McCreight E. Organization and maintenance of large ordered indizes. Acta Informatica. 2012;1:173.

Md. Rafiqul Islam, Raquib Uddin SM. An external sorting algorithm using merging. Malaysian Journal of Computer Science. 2015;18(1):40−49.