CFP last date
16 December 2024
Call for Paper
January Edition
IJAIS solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 16 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Ordered Frequent Itemsets Matrix Based On Fp-Tree Structure And Apriori Algorithm

Abdulkader M. Al-Badani Abdualmajed A. Al-Khulaidi
Random Articles
Reseach Article

Adaptive Merge Sort

Published on June 2014 by Nenwani Kamlesh, Vanita Mane, Smita Bharne
journal_cover_thumbnail

International Conference and workshop on Advanced Computing 2014
Foundation of Computer Science USA
ICWAC2014 - Number 2
June 2014
Authors: Nenwani Kamlesh, Vanita Mane, Smita Bharne
68b6e940-a488-47d6-a78a-48a9cb8d84d1

Nenwani Kamlesh, Vanita Mane, Smita Bharne . Adaptive Merge Sort. International Conference and workshop on Advanced Computing 2014. ICWAC2014, 2 (June 2014), 0-0.

@article{
author = { Nenwani Kamlesh, Vanita Mane, Smita Bharne },
title = { Adaptive Merge Sort },
journal = { International Conference and workshop on Advanced Computing 2014 },
issue_date = { June 2014 },
volume = { ICWAC2014 },
number = { 2 },
month = { June },
year = { 2014 },
issn = 2249-0868,
pages = { 0-0 },
numpages = 1,
url = { /proceedings/icwac2014/number2/650-1435/ },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Proceeding Article
%1 International Conference and workshop on Advanced Computing 2014
%A Nenwani Kamlesh
%A Vanita Mane
%A Smita Bharne
%T Adaptive Merge Sort
%J International Conference and workshop on Advanced Computing 2014
%@ 2249-0868
%V ICWAC2014
%N 2
%P 0-0
%D 2014
%I International Journal of Applied Information Systems
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.

References
  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.
Index Terms

Computer Science
Information Sciences

Keywords

Sorting Merge Sort Adaptive.