Google scholar arxiv informatics ads IJAIS publications are indexed with Google Scholar, NASA ADS, Informatics et. al.

Call for Paper

-

July Edition 2023
International Journal of Applied Information Systems solicits high quality original research papers for the July 2023 Edition of the journal. The last date of research paper submission is June 15, 2023.

Adaptive Merge Sort

Nenwani Kamlesh, Vanita Mane, Smita Bharne Published in Advanced Computing

Adaptive Merge Sort
IJAIS Proceedings on International Conference and workshop on Advanced Computing 2014
Year of Publication: 2014
© 2014 by IJAIS Journal
Series ICWAC 2014 Number 2
Authors Nenwani Kamlesh, Vanita Mane, Smita Bharne
Download full text

  1. Nenwani Kamlesh, Vanita Mane and Smita Bharne. Article: Adaptive Merge Sort. IJAIS Proceedings on International Conference and workshop on Advanced Computing 2014 ICWAC 2014(2):21-24, June 2014. BibTeX

    @article{key:article,
	author = "Nenwani Kamlesh and Vanita Mane and Smita Bharne",
	title = "Article: Adaptive Merge Sort",
	journal = "IJAIS Proceedings on International Conference and workshop on Advanced Computing 2014",
	year = 2014,
	volume = "ICWAC 2014",
	number = 2,
	pages = "21-24",
	month = "June",
	note = "Published by Foundation of Computer Science, New York, USA"
}

Abstract

Merge Sort is a comparison based sorting algorithm with O(n log n) computational complexity. It is not adaptive to existence of ordering among the elements. Thus, has the same computational complexity in any case. In this paper, we propose Adaptive Merge Sort algorithm which is adaptive to existence of ordering among the elements in the list. Adaptive Merge sort has the complexity of O(n) for best case instead of O(n log n). Thus improvement requires additional space of O(n). The improvement in the performance is justified with an experimental analysis of the algorithm.

Reference

  1. C. E. Leiserson, R. L. Rivest, C. Stein, and T. H. Cormen, Introduction to algorithms. The MIT press, 2001.
  2. A. Tenenbaum, Data Structures Using C. Pearson Education, 1990. [Online]. Available: http://books. google. co. in/books?id=X0Cd1Pr2W0gC.
  3. D. E. Knuth, "The art of computer programming, vol. 3: Sorting and searching," 1973. "
  4. Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms. " ACM Computing Surveys (CSUR) 24. 4 (1992): 441-476.
  5. Lipschutz, Data Structures With C. McGraw-Hill Ed- ucation (India) Pvt Limited, 2011. [Online]. Available: http://books. google. co. in/books?id=YJQIOLgFnnYC.
  6. Symvonis, Antonios. "Optimal stable merging. " The Computer Journal 38. 8 (1995): 681-690.
  7. Brown, Mark R. , and Robert E. Tarjan. "A fast merging algorithm. " Journal of the ACM (JACM) 26. 2 (1979): 211-226.

Keywords

Sorting, Merge Sort, Adaptive.