Could someone please help me out Give a modified version of the mergeSort algori

Question

Could someone please help me out

Give a modified version of the mergeSort algorithm so that given an array A of n numbers, it outputs the number of pairs i < j such that A[i] > A[j]. The running time of your algorithm must still be T (n) = 2T(n/2) + C1 n + C2 where C1 and C2 are constants. For example, on given array A = [5 2 6 7 1], the algorithm should return 5, because 5 > 2,5 > 1,6 > 1, 7 > 1

This is the merge sort algortihm:

Algorithm mergeSort(A, i, j)

Input: An array A of numbers, the bounds i and

j for the elements to be sorted

Output: A[ i...j ] is sorted

if ( i < j ) { /* We have at least two elements to sort */

mid <

Explanation / Answer

Merge sort Algorithm:

MergeSort(array A, int i, int j)

{

     if( i < j)

     {

          mid=(i+j)/2;

          MergerSort(A, i, mid)

          MergerSort(A, mid+1,j)

          Merger(A, i, mid, j)

}

}

Merge(array A, int i, int mid, int j )

{

     array B[i..j]

     p=r=i;

     q=mid+1;

     while(p <= q and q <= r)

     {

          if(A[p] <= A[r])

              B[r++]=A[p++];

          Else B[r++] = A[q++];

}

While(p<=mid)

     B[r++]=A[p++]

While (j<=r)

     B[r++] =A[q++}

For p=i to j

     Do A[p] =B[p]

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.