Optimal External Merge Sorting Algorithm with Smart Block Merging

Authors: Mir Hadi Seyedafsari, Iraj Hasanzadeh

Abstract:

Like other external sorting algorithms, the presented algorithm is a two step algorithm including internal and external steps. The first part of the algorithm is like the other similar algorithms but second part of that is including a new easy implementing method which has reduced the vast number of inputoutput operations saliently. As decreasing processor operating time does not have any effect on main algorithm speed, any improvement in it should be done through decreasing the number of input-output operations. This paper propose an easy algorithm for choose the correct record location of the final list. This decreases the time complexity and makes the algorithm faster.

Keywords: External sorting algorithm, internal sortingalgorithm, fast sorting, robust algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1073144

References:

[1] Aggarwal. A. & vitter. J. S, "Input / out put Complexity Of Sorting and related problem", Communications of the ACM, 1988
[2] Arge. L. & Knudsen. M. & Larsen. K, "A general lower bound on the I/O complexity of comparision-based algorithms", LNCS 709, 1993, pages 83-94.
[3] Baker. M, "Discussion of Sorting Algorithms", Mark chris Soft Home, 1999.
[4] Chen. S.Y, "Complexity Estimation", York University, 1999.
[5] Carlson. D, "External Sorting", Saint Vincent College, 2004.
[6] Floros. I, "Analysis of Internal Computer Sorting", Journal of ACM (JACM), 1999.
[7] Neapolitan. R. E. & Naimipour. K, "Foundations of Algorithms", Jones and Barlett publishers, 1998.
[8] Pang. H. & Carey. M. J. & Livny. M, "Memory-Adaptive External Sorting", Wisconsin-madison University pages 618-628, 1993.
[9] Saltenis. S, "External-Memory Sorting", ACM, 2002.
[10] wang. P. Y, "A symptotic Complexity", George Mason University, 2003.
[11] Rafiqul. I, Nasim. A, Nur. I, Shohorab. H, "A new external sorting algorithm with no additional disk space", Information Processing Letters, v.86 n.5, pages.229-233, 15 June 2003.
[12] Martin. G, Christoph. K, Nicole. S, "Tight lower bounds for query processing on streaming and external memory data", Theoretical Computer Science, v.380 n.1-2, pages.199-217, June, 2007.
[13] Goetz. G, "Implementing sorting in database systems", ACM, September 2006.
[14] John. Y, Justin. Z, "Compression techniques for fast external sorting", Springer-Verlag New York, Pages: 269 - 291, April 2007.