Merge Sort Algorithm

Merge sort algorithm is an efficient, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Conceptually, a merge sort works as follows:

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted). 2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

In comparison to Quick sort the divide part in Merge sort is simple, while the merging part is complex. Quick sort can sort “inline” in an existing collection, e.g. it does not have to create a copy of the collection while Mergesort requires a copy.

Binary Search
Linear or Sequential Search Explanation
Performance
  • Worst-case performance :- O(n log n)
  • Best-case performance :- O(n log n) typical, O(n) natural variant
  • Average performance :- O(n log n)
  • Worst-case space complexity :- О(n) total, O(n) auxiliary
Java Program of Merge Sort Algorithm

Output

Input Array before Merge Sort. 38 27 43 3 9 82 10 Sorted Array after Merge Sort. 3 9 10 27 38 43 82

Some theory part of this article uses material from the Wikipedia article “Merge Sort”, which is released under the CC BY-SA 3.0.

It's good to share...Share on FacebookTweet about this on TwitterShare on LinkedInPin on PinterestShare on Google+Email this to someone

Leave a Reply

Your email address will not be published. Required fields are marked *