Answer:
The algorithm is very similar to the algorithm of counting inversions. The only change is that here we separate the counting of significant inversions from the merge-sort process.
Algorithm:
Let A = (a1, a2, . . . , an).
Function CountSigInv(A[1...n])
if n = 1 return 0; //base case
Let L := A[1...floor(n/2)]; // Get the first half of A
Let R := A[floor(n/2)+1...n]; // Get the second half of A
//Recurse on L. Return B, the sorted L,
//and x, the number of significant inversions in $L$
Let B, x := CountSigInv(L);
Let C, y := CountSigInv(R); //Do the counting of significant split inversions
Let i := 1;
Let j := 1;
Let z := 0;
// to count the number of significant split inversions while(i <= length(B) and j <= length(C)) if(B[i] > 2*C[j]) z += length(B)-i+1; j += 1; else i += 1;
//the normal merge-sort process i := 1; j := 1;
//the sorted A to be output Let D[1...n] be an array of length n, and every entry is initialized with 0; for k = 1 to n if B[i] < C[j] D[k] = B[i]; i += 1; else D[k] = C[j]; j += 1; return D, (x + y + z);
Runtime Analysis: At each level, both the counting of significant split inversions and the normal merge-sort process take O(n) time, because we take a linear scan in both cases. Also, at each level, we break the problem into two subproblems and the size of each subproblem is n/2. Hence, the recurrence relation is T(n) = 2T(n/2) + O(n). So in total, the time complexity is O(n log n).
Explanation:
