Introduction:In computer science, merge sort (also commonly known or spelled as “mergesort”) is an efficient, general purpose & comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output. Merge sort is a divide and conquer algorithm that was invented by “John Von Neuman” in 1945.A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine & von Neuman in “1948.”
Eg: First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally, all the elements are sorted and merged. Sorting algorithms are generally used for sorting of Telephone Directory and Dictionary, etc
A sorting algorithm, after sorting the contents, does not change the sequence of similar content in which they appear is called as Stable Sort. This in simple language means that a sorting algorithm is said to be stable if two objects with equal values appear in the same order in sorted output as they appear in the input array to be sorted.
Informally, stability means that equivalent elements retain their relative positions, after sorting. Several common sorting algorithms are stable by nature, best case is a Merge Sort.
Time Complexity of Merge Sort:
Merge Sort is quite fast, and Also has a time complexity of O(n*log n). As well as also a stable sort, which means the “equal” elements are ordered in the same order in the sorted list.
The time complexity of merge sort is as follows:
Worst Case Time Complexity [ Big-O]: O(n*log n)
Best Case Time Complexity [Big-omega]: O(n*log n)
Average Time Complexity [Big-theta]: θ(n*log n)
Space Complexity of Merge Sort:
Space complexity is a function describing the amount of memory (space) an algorithm takes in terms of the amount of input to the algorithm. We often speak of “extra” memory needed, not counting the memory needed to store the input itself.
Space complexity of Merge Sort: O(n)
Conceptually, a merge sort works as follows:
1. Divide the unsorted list into n sub lists, each containing one element (a list of one element is considered sorted).
2. Repeatedly Merge sub lists to produce new sorted sub lists until there is only one sub list remaining. This will be the sorted list.
Let us Consider an Example: Unsorted List of Array [38,27,43,3,9,82,10]
STEP 1: Divide array of size 7 into two halves.
STEP 2: Divide arrays Further into halves.
STEP 3: Divide arrays into equal halves.
Step 4: Now will merge them in a Sorted Array. Compare 38 and 27, 43 and 3, 9 and 82, and 10 to prepare target list with 2 values in ordered form.
STEP 5: Now will merge two data values and put them in ordered form.
STEP 6: Now we will merge 4 data values and put them in ordered form.
Step 7: Will Obtain Final Sorted Array.
Advantage Of Merge Sort Algorithm:
1. More efficient and works faster than Quick sort in case of large Data sets.
2. Good for Sorting Slow-Access Data.
3. Excellent for sorting data that are normally accessed sequentially.
Disadvantages Of Merge Sort Algorithm:
1. The running time of merge sort algorithm is 0(n log n). Which turns out to be the worst case. When in use.
2. Algorithm requires additional memory space of 0(n) for the temporary array TEMP.
Applications Of Merge Sort:
1. It is the best Sorting technique used for sorting Linked Lists.
2. Used for Counting inversions in a List.
3. Also Widely Used for External Sorting Applications.