Merge Sort Calls – You are given an array A of N elements…

You are given an array A of N elements. You want to sort it in non-decreasing order using merge-sort algorithm. It involves using a recursive function mergeSort(A,l,r):

  1. If the segment [l,r) is already sorted in non-decreasing order return.
  2. Let mid = (l+r)/2.
  3. Call mergeSort(A, l, mid)
  4. Call mergeSort(A, mid, r)
  5. Merge segments [l, mid) and [mid, r), making the segment [l, r) sorted in non-descending order.

The initial call made is mergeSort(A,0,N). Find the number of times mergeSort function is called to sort the given array in non-decreasing order.

Related Posts

Close Bitnami banner