Posted by: atri | November 20, 2009

## Lect 32: Merge-Count Algorithm

(Guest post by Jake Tangel)

Today in class we went over the merge count algorithm

Merge-count$(A,B)$

1. keep pointer($i$) to $A$ and pointer($j$) to $B$ ($i=j=1$)
2. $\mathrm{Inv} = 0$
3. repeat until $i=m$ or $j = m$
• if $A[i] \le B[j]$ add $A[i++]$ to $C$
• else $\mathrm{Inv} += m - i+1$ and add $B[j++]$ to $C$
4. If one of arrays isn’t done append it to $C$
5. return $(\mathrm{Inv},C)$

Example of merge count two sorted arrays. you look at the column to the left see how many on the right are less then it that is the number of inversions. next take a look at the columns on the right and  then see how many values on the left column are greater then it.

$1\leftarrow 2$            $1\rightarrow 4$
$1\leftarrow 3$            $4\rightarrow 2$
$4\leftarrow 8$            $5\rightarrow 2$
$4\leftarrow 10$           $6\rightarrow 2$
$10$ inversions   $10$ inversions

Then $C$ will be
$1$
$2$
$3$
$4$
$5$
$6$
$8$
$10$

• $a_i \le b_j$ then  send $a_i$ to output
• $a_i > b_j$ then # of inversions $b_j$ participates in is $m-i +1$

Then we went over some computational geometry and concluded that the brute force algo runs in time $O(n^2)$ which is a very poor run time, and next class were gonna go over a divide and conquer version of the algo.