As volume of information is growing up day by day
in the world around us and prerequisite of some optimized
operations is sorted list, the efficient and cost effective sorting
algorithm is required. There are several number of sorting
algorithms but still now this field has attracted a great deal of
research, perhaps due to the complexity of solving it efficiently
despite of its simple and familiar statements. An algorithm is
chosen according to one’s need with respect to space complexity
and time complexity. Now days, space is available
comparatively in cheap cost. So, time complexity is a major
issue for an algorithm. Here, the presented approach is to
achieve linear time complexity using divide and conquer rule by
partitioning a problem into n (input size) sub problem, then
these sub problems are solved recursively. So, asymptotic
efficiency of this algorithm is very high with respect to time.
Sanjib Palui : has completed his bachelor degree in Information
Technology and master degree in Software Engineering in the year of
2012 and 2014 respectively. Then he has joined Indian Statistical
Institute as Project Linked Person in the unit of Computer Vision &
Pattern Recognition (CVPR). He is working on Data Structure &
algorithm, Image Processing and Optical Character Recognition
fields.
Dr. Somsubhra Gupta : is presently the Assistant Professor of the
Department of Information Technology, JIS College of Engineering
(An Autonomous Institution). He is graduated from the University of
Calcutta and completed his Masters from Indian Institute of
Technology, Kharagpur. He received Ph. D. award entitled
“Multiobjective Decision Making in Inexact Environment using
Genetic Algorithm: Theory and Applications” form University of
Kalyani. His area of teaching is Algorithm and allied domains and
research area is Machine Intelligence. In research, he has around 56 papers including Book Chapters so far in National / International
Journal / Proceedings and over 40 citations. He is Principal
Investigator / Project Coordinator to some Research projects (viz.
RPS scheme AICTE). He was the Convener of International
Conference on Computation and Communication Advancement
(IC3A-2013). He is invited in the Technical Programme Committee of
number of Conferences, delivered as an invited speaker, an INS
(Elsevier Science) reviewer and attended NAFSA-2013 conference of
international educators at St. Louis, Missouri, USA
sorting
searching
divide and conquer
algorithm
asymptotic efficiency
space complexity
time complexity
recursion
The main advantage of the presented algorithm is its
speed. Selection of sorting algorithm is application and
situation dependent but this algorithm works well in every
field. For real life sorting problem, asymptotic time
complexity of this algorithm is linear and space
complexity is --for the usage of two dimensional
memory which makes it faster.
[1] D.E. Kunth, Sorting and Searching, The Art of Computer
Programming: Vol. 3, Addison-Wesley, 1973. Second
Edition, 1998.
[2] D.E. Kunth, Fundamental Algorithms, The Art of
Computer Programming: Vol.1, Addison-Wesley, 1968.
Third Edition, 1997.
[3] D. E. Kunth, Seminumerical Algorithms, The Art of
Computer Programming: Vol.2, Addison-Wesley,1969.
Third Edition 1997.
[4] D. E. Kunth, Big omicron and big omega and big theta.
SIGACT News, 8(2)18-23,1976.
[5] T. Cormen, C. Leiserson, R. Rivest, and C. Stein,
Introduction to Algorithm McGraw Hill, 2001.
[6] A. V. Aho , J E. Hopcroft and J. D. Ullman The Design
and Analysis of Computer Algorithms. Addison-
Wesley,1974.
[7] A.V. Aho , J. E. Hopcroft and J. D. Ullman Data
Structures and Algorithms.Addison-Wesley,1983
[8] R. Lavore, Arrays, Big O Notation and Simple Sorting.
Data Structures and Algorithms in Java (2nd Edition).
Sams, 978-0-672-32453-6..
[9] S. Baase and A. V. Gelder. Computer Algorithm:
Introduction to Design and Analysis. Addison-Wesley,
Third edition, 2000.
[10] A. Aggarwal and J. S. Vitter.The input/output
Complexity of sorting and related
problems.Communication of the ACM,31(9):1116-
1127,1998.
[11] M. Akra and L. Bazzi.On the solution of linear
recurrence equation.Computational Optimization and
Application,10(2):195-210,1998.
[12] J. L. Bentley, D. Haken and J. B. Saxe. A general
method for solving divides and conquers recurrence.
SIGACT News, 12(3):36-44,1980.
[13] S. Jadoon, S. F. Solehria, M. Qayum, “Optimized
Selection Sort Algorithm is faster than Insertion Sort
Algorithm: a Comparative Study” International
Journal of Electrical & Computer Sciences IJECSIJENS,
Vol: 11 No: 02, 2011.
[14] Y. Yang, P. Yu, Y. Gan, (2011) “Experimental Study
on the Five Sort Algorithms”,International Conference
on Mechanic Automation and Control Engineering
(MACE).
[15] W. Min, “Analysis on 2-Element Insertion Sort
Algorithm”, International Conference on Computer
Design And Appliations (ICCDA), 2010.
[16] E. Kapur, P. Kumar and S. Gupta-“Proposal Of A Two
Way Sorting Algorithm And Performance Comparison
With Existing Algorithms”- International Journal of
Computer Science, Engineering and Applications
(IJCSEA) Vol.2, No.3, June 2012
[17] S. Z. Iqbal, H. Gull, A. W. Muzaffar, “A New Friends
Sort Algorithm”,IEEE Second International
Conference on Computer Science and Information
Technology, 2009.
[18] J.L. Bentley and R. Sedgewick, Fast Algorithms for
Sorting and Searching Strings, ACM-SIAM SODA”
97, 360-369, 1997.
[19] B. R. and L. S., A Fast Sort, Computer Journal of Byte
Magazine, vol. 16, no. 4, pp. 315-315, 1991.
[20] C.A.Hoare. Algorithm 63 (PARTITION) and
algorithm (FIND). Communications of the
ACM,4(7),321-322,1961.
[21] R.W.Floyd and R.L.Rivest.Expected time bounds for
selection. Communications of the ACM ,18(3):165-
172, 1975.
[22] M.D.McIlroy. A killer adversary for quicksort.
Software -Practice and Experience, 29(4):341-
344,1999.
