Write a Program Merge Sort in C++

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: