Merge Sort: Merge Sort algorithm is based on Divide and Conquer theory. In this methodology, unsorted array list is divided into small sub-arrays. The sub-array elements are sorted and then merge into a single sorted array. Dividing of array into sub-array is done with the help of merge-sort method and sorting sub-array element and merging it to a single sorted array is done with the help of merge method. Time complexity of merge sort algorithm is O(n) where n=r-p+1. Have a look at below diagram, it is the buttom-up view of merge sort algorithm.
Merge Sort:Algorithm:
MERGE-SORT (A, p, r)
1. IF p < r // Check for base case
2. THEN q = FLOOR[(p + r)/2] // Divide step
3. MERGE (A, p, q) // Conquer step.
4. MERGE (A, q + 1, r) // Conquer step.
5. MERGE (A, p, q, r) // Conquer step.
Program:
Output:
