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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: