The Merge Sort algorithm is a sorting algorithm that is based on the Divide and Conquer paradigm. In this algorithm, the array is initially divided into two equal halves and then they are combined in a sorted manner.
Algorithm:
- step 1: start
- step 2: declare array and left, right, mid variable
- step 3: perform merge function.
if left > right return mid= (left+right)/2 mergesort(array, left, mid) mergesort(array, mid+1, right) merge(array, left, mid, right)
- step 4: Stop
Follow the steps below the solve the problem:
MergeSort(arr[], l, r)
If r > l
- Find the middle point to divide the array into two halves:
- middle m = l + (r – l)/2
- Call mergeSort for first half:
- Call mergeSort(arr, l, m)
- Call mergeSort for second half:
- Call mergeSort(arr, m + 1, r)
- Merge the two halves sorted in steps 2 and 3:
- Call merge(arr, l, m, r)
Time Complexity: O(N log(N)), Sorting arrays on different machines. Merge Sort is a recursive algorithm and time complexity can be expressed as following recurrence relation.
T(n) = 2T(n/2) + θ(n)