CODEWITHSUNDEEP
algorithmsorting
John Rawls
John Rawls

Reputation: 259

Why is divide and conquer inversion count n*log(n)?

A lot of resources that I've viewed said that divide and conquer inversion counting method has runtime of nlog(n) but I don't understand why. I know merge sort has nlog(n) time because the number of dividing arrays until the base case is log(n) and the runtime of merging is (n) on each time we need to merge two arrays.

But when we're "piggy-backing" on top of merge sort we need to compare two halves of an array:

[a,b,c] and [d,e,f]

"a" needs to be compared with "d" and "e" and "f" worst-case scenario and so on and so forth for all elements in the left array. So it seems to be that this alone would have runtime of n^2/4 so wouldn't the runtime of divide and conquer inversion algo be n^2log(n)?

Upvotes: 0

Views: 344

Answers (1)

Lior Kogan
Lior Kogan

Reputation: 20648

[a,b,c] and [d,e,f]

"a" needs to be compared with "d" and "e" and "f" worst-case scenario

The loop

while (not at end of A && not at end of B)

always has O(|A|+|B|) steps, no matter what the results of the comparisons are. There is no best-case nor worst-case for Merge-and-Count.

Sort-and-Count(L)

if list L has one element
    return (0, L)

Divide the list into two halves A and B
(rA, A) ← Sort-and-Count(A)
(rB, B) ← Sort-and-Count(B)
(rC, L) ← Merge-and-Count(A, B)
r = rA + rB + rC
return (r, L)

Merge-and-Count (A, B)

    curA = 0; curB = 0;
    count = 0;
    mergedList = empty list

    while (not at end of A && not at end of B)
        a = A[curA]; b = B[curB];
        if (a < b)                             // only one comparison
            append a to mergedList;
            curA++;
        else
            append b to mergedList;
            curB++;
            count = count + num elements left in A

    if (at end of A) 
        append rest of B to mergedList;
    else
        append rest of A to mergedList;

    return (count, mergedList);

Upvotes: 1

Related Questions