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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:58706", author = "Mir Hadi Seyedafsari and Iraj Hasanzadeh", title = "Optimal External Merge Sorting Algorithm with Smart Block Merging", 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.", volume = "4", number = "2", pages = "296-4", }