Performance Analysis of a Faster In−place External Sorting Algorithm
Asaduzzaman Nur Shuvo
Department of Information and Communication Engineering, Noakhali Science and Technology University, Noakhali − 3814, Bangladesh.
Apurba Adhikary *
Department of Information and Communication Engineering, Noakhali Science and Technology University, Noakhali − 3814, Bangladesh and Electronics and Communication Engineering Discipline, Khulna University, Khulna − 9208, Bangladesh.
Md. Bipul Hossain
Department of Information and Communication Engineering, Noakhali Science and Technology University, Noakhali − 3814, Bangladesh.
Sultana Jahan Soheli
Department of Information and Communication Engineering, Noakhali Science and Technology University, Noakhali − 3814, Bangladesh.
*Author to whom correspondence should be addressed.
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.