###### 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. 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.