Explain Merge Sort in detail?

Software Development
#1

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)