Optimal External Merge Sorting Algorithm with Smart Block Merging

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.

Authors:

• Mir Hadi Seyedafsari
• Iraj Hasanzadeh

Keywords:

• External sorting algorithm
• internal sortingalgorithm
• fast sorting
• robust algorithm.

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.