Abstract:
This paper aims at introducing a new sorting algorithm which sorts the elements of an array In Place. This algorithm has O(n) best case Time Complexity and O(n log n) ave...Show MoreMetadata
Abstract:
This paper aims at introducing a new sorting algorithm which sorts the elements of an array In Place. This algorithm has O(n) best case Time Complexity and O(n log n) average and worst case Time Complexity. We achieve our goal using Recursive Partitioning combined with In Place merging to sort a given array. A comparison is made between this particular idea and other popular implementations. We finally draw out a conclusion and observe the cases where this outperforms other sorting algorithms. We also look at its shortcomings and list the scope for future improvements that could be made.
Published in: 2016 International Conference on Advanced Communication Control and Computing Technologies (ICACCCT)
Date of Conference: 25-27 May 2016
Date Added to IEEE Xplore: 26 January 2017
ISBN Information:
References is not available for this document.
Contents Select All
1.
D. E. Knuth, "Sorting and Searching" in The Art of Computer Programming, vol. 3rd.
2.
You Yang, Ping Yu and Yan Gan, "Experimental Study on the Five Sort Algorithms", International Conference on Mechanic Automation and Control Engineering (MACE), 2011.
3.
W. A. Martin, "Sorting", ACM Comp Survey., vol. 3, no. 4, pp. 147-174, 1971.
4.
Jyrki Katajainen, Tomi Pasanen and Jukka Teuhola, "Practical in-place mergesort", Nordic Journal of Computing Archive, vol. 3, no. 1, 1996.
5.
R. Cole, "Parallel Merge Sort", Proc. 27th IEEE Symp. FOCS, pp. 511516, 1988.
6.
Symvonis Antonios, "Optimal stable merging", The Computer Journal, vol. 38, no. 8, pp. 681-690, 1995.
7.
Wang Xiang, "Analysis of the Time Complexity of Quick Sort Algorithm", Information Management Innovation Management and Industrial Engineering (ICIII) International Conference, 2011.
8.
Kushagra Shrinu, Lopez Alejandro, J. Ian Munro and Aurick Qiao, "Multi-Pivot Quicksort: Theory and Experiments", Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX), pp. 47-60, 2014.
9.
Nadir Hossain, Md. Golam Rabiul Alma, Md. Amiruzzaman and S.M. Moinul Quadir, "An Efficient Merge Sort Technique that Reduces both Times and Comparisons", Information and Communication Technologies: From Theory to Applications International Conference, 2004.
10.
L. T. Pardo, "Stable sorting and merging with optimal space and time bounds", SIAM Journal on Computing, vol. 6, no. 2, pp. 351-372, 1977.
11.
Jeffrey Ullman, John Hopcroft and Alfred Aho, "The Design and Analysis of Computer Algorithms", 1974.
12.
E. Horowitz and S. Sahni, "Fundamentals of Data Structures" in , Rockville:Computer Science Press, 1976.
13.
Guigang Zheng, Shaohua Teng Guangzhou, Wei Zhang and Xiufen Fu, "A cooperative sort algorithm based on indexing", Computer Supported Cooperative Work in Design 13th International Conference, 2009.
14.
Bing-Chao Huang and Michael A. Langston, "Practical in-place merging", Communications of the ACM CACM Homepage table of contents archive, vol. 31, no. 3, 1988.
15.
A. Symvonis, "Optimal stable merging", Computer Journal, vol. 38, pp. 681-690, 1995.
16.
F. K. Hwang and S. Lin, "A Simple algorithm for merging two disjoint linear ordered sets", SIAM Journal on Computing, 1972.
17.
E. C. Hovarth, "Stable sorting in asymptotically optimal time and extra space", Journal of the ACM, pp. 177-199, 1978.
18.
S. Dvorak and B. Durian, "Stable linear time sub linear space merging", The Computer Journal, vol. 30, pp. 372-375, 1987.
19.
J. Chen, "Optimizing stable in-place merging", Theoretical Computer Science, vol. 302, no. 1/3, pp. 191-210, 2003.
20.
Rohit Yadav, Kratika Varshney and Nitin Verma, "Analysis of Recursive and Non-Recursive Merge Sort Algorithm", International Journal of Advanced Research in Computer Science and Software Engineering, vol. 3, no. 11, November 2013.
