IN-PLACE MERGING AND EXTERNAL SORTING ALGORITHM WITH NO ADDITIONAL DISK SPACE

Md. Rafiqul  Islam; S. M. Masud  Rana; Md. Monir   Hossain; Wahida  Nusrat

doi:10.53808/KUS.2006.7.1.0406-E

Authors

Md. Rafiqul Islam Computer Science and Engineering Discipline, Khulna Univesrsity, Khulna 9208, Bnagladesh
S. M. Masud Rana Computer Science and Engineering Discipline, Khulna Univesrsity, Khulna 9208, Bnagladesh
Md. Monir Hossain Computer Science and Engineering Discipline, Khulna Univesrsity, Khulna 9208, Bnagladesh
Wahida Nusrat Computer Science and Engineering Discipline, Khulna Univesrsity, Khulna 9208, Bnagladesh

DOI:

https://doi.org/10.53808/KUS.2006.7.1.0406-E

Keywords:

external sorting, runs, quick sort, algorithm, in-place merging

Abstract

The performance of external sorting mainly depends on its I/O and time complexities. In this paper we represent a more efficient external sorting algorithm with no additional disk space. This algorithm uses Quick sort to produce runs in the first phase. It uses special in-place merging technique in the second phase. The algorithm excels in sorting a huge file, which is larger than the available internal memory of the computer. The algorithm creates no backup file for manipulating huge records. Usually the external sorting algorithm needs additional disk space in merging phase. This algorithm saves disk space, since it does not use any backup file or additional disk space. Here we have briefly reviewed the external sorting algorithms, which do not use additional disk space. The I/O and time complexities of the proposed algorithm are analyzed and compared with that of other similar algorithms. We have found that the I/O complexity of the proposed algorithm is less than that of other similar algorithms (algorithms which do not need additional disk space) with the same time complexity.

Downloads

Download data is not yet available.

References

Adnan, M.N.; Islam, M.R.; Islam, M.N. and Hossen, M.S. 2202. A faster hybrid external sorting algorithm with no additional disk space. Proceedings of International Conference on Computer and Information Technology (ICCIT), 27-28 December, Dhaka, Bangladesh, pp. 6-9.

Dufrene, W.R. and Lin, F.C. 1992. An efficient sorting algorithm with no additional space. Computer Journal, 35(3): 308-310.

Islam, M. R.; Raquib Uddin, S.M., and Chinmoy, R. 2005. Computational complexities of the external sorting algorithm with no additional disk space. International Journal of Computer, Internet and Management, 13(3): 60-68.

Islam, M.R.; Adnan, M.N.; Islam, M.N and Hossen, M.S. 2003. A new external sorting algorithm with no additional disk space. Information Processing Letters, 86: 229- 233.

Knuth, D.E. 1973 Sorting and Searching, the Art of Computer Programming. Vol. 3, Addison–Wesley, Reading, MA., pp. 247-299.

Leu, F.C.; Tsai, Y.T. and Tang, C. 2000. An efficient external algorithm. Information Processing Letters, 75: 159-163.

Nodine, M.S. and Vitter, J.S. 1995. Greet sort: An optimal sorting algorithm for multiple disks. Journal of the Association of Computing Machinery (ACM), 42(4): 919-933.

Rana, M.S.M.; Hossain, M.M. and Nusrat, W. 2005. A new external sorting algorithm using special in-place merging technique with no additional disk, space. Undergraduate Thesis (unpublished), Computer Science and Engineering Discipline, Khulna University.

Uddin, S.M.R.; Islam, M.R. and Chinmoy, R. 2003. Complexities of an efficient external sorting algorithm with special cases, proceedings of Conference on Computer and Information Technology (ICCIT), 19-21 December, Dhaka, Bangladesh, pp. 126-129.

Wegner, L. and Teuhola, J.I. 1989. The external Heapsort. IEEE Transaction on Software Engineering, 5(7): 917-925.