Merge Sort Algorithm (with Example) with C++ Code | Sorting Algorithms | Data Structures & Algorithms

> Merge Sort Algorithm is a Divide & Conquer algorithm. It divides input array in two halves, calls itself for the two halves(recursively) and then merges the two sorted halves. A separate merge() function is used for merging two halves. Merge sort is one of the most efficient sorting algorithms.
>> Time Complexity: O(nlog(n))
Working –
There are 3 Phases (4 major steps) in the Merge Sort Algorithm –
  1. Division Phase – Divide the array(list) into 2 halves by finding the midpoint of the array(list).
    1. Midpoint (m) = (left + right)/ 2
    2. Here left is the starting index & right is the last index of the array(list)
  2. Recursion Phase –
    1. Call Merge Sort on the left sub-array (sub-list)
    2. Call Merge Sort on the right sub-array (sub-list)
  3. Merge Phase –
    1. Call merge function to merge the divided sub-arrays back to the original array.
    2. Perform sorting of these smaller sub arrays before merging them back.
Merge Sort Algorithm(Pseudo Code) –
C++ Program to Implement Merge Sort –
YouTube video tutorials –

Leave a Reply

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