What is the purpose of the MERGESORT algorithm?

[evinda]

Hello! (Mmm)

I am looking at the following algorithm:

MERGESORT(A,l,r){
   if (R==L) return;
   MERGESORT(A,l,floor((r+l)/2));
   MERGESORT(A,floor((r+l)/2)+1,r);
   return MERGE(A,l,r,floor((r+l)/2));

What does the above algorithm do? Could you explain it to me? (Thinking)

 

[I like Serena]

Hello! (Mmm)

I am looking at the following algorithm:

MERGESORT(A,l,r){
   if (R==L) return;
   MERGESORT(A,l,floor((r+l)/2));
   MERGESORT(A,floor((r+l)/2)+1,r);
   return MERGE(A,l,r,floor((r+l)/2));

What does the above algorithm do? Could you explain it to me? (Thinking)

Hey! (Wave)

This merge-sort algorithm splits an array into 2 halves.
Then it "merge-sorts" each half.
The resultant array is "merged".

The same procedure is apply to any of those parts. (Nerd)

 

[evinda]

Hey! (Wave)

This merge-sort algorithm splits an array into 2 halves.
Then it "merge-sorts" each half.
The resultant array is "merged".

The same procedure is apply to any of those parts. (Nerd)

Could you give me an example, in order to apply the algorithm? (Wasntme)

 

[I like Serena]

Could you give me an example, in order to apply the algorithm? (Wasntme)

Well, first you need the algorithm for MERGE.
Can you tell us what it is? (Wondering)

And then we should try to apply it to for instance (3,5,2,7)... (Thinking)
I can already tell you that (2,3,5,7) will come out! (Smile)

 

[evinda]

Well, first you need the algorithm for MERGE.
Can you tell us what it is? (Wondering)

This is the algorithm [m] MERGE [/m] :

MERGE(A,p,q,r)
   n1=q-p+1
   n2=r-q;
   we create the arrays L[1 .. n1+1] and R[1 .. n2+1]
   for i=1 till n1
        L[i]=A[p+i-1]
   for j=1 till n2
        R[j]=A[q+j]
   L[n1+1]=oo
   R[n2+1]=oo
   i=1
   j=1
   for k=p till r
        if (L[i]<=R[j])
           then A[k]=L[i]
                  i=i+1
           else A[k]=R[j]
                 j=j+1

And then we should try to apply it to for instance (3,5,2,7)... (Thinking)
I can already tell you that (2,3,5,7) will come out! (Smile)

Before executing the command [m] return MERGE(A,l,r,floor((r+l)/2)); [/m], the following commands are executed:

[m] MERGESORT(A,0,1) [/m]

[m] MERGESORT(A,0,0) [/m]

[m] MERGESORT(A,2,3) [/m]

[m] MERGESORT(A,2,2) [/m]

[m] MERGESORT(A,3,3) [/m]Right? (Thinking)
What do we get from these calls? (Callme) (Thinking)

 

[I like Serena]

This is the algorithm [m] MERGE [/m] :

That's quite a complicated algorithm! (Sweating)

Well, it may suffice that it merges 2 sorted arrays into a new array, that is then sorted. (Whew)

Before executing the command [m] return MERGE(A,l,r,floor((r+l)/2)); [/m], the following commands are executed:

Right? (Thinking)
What do we get from these calls? (Callme) (Thinking)

Well, [m] MERGESORT(A,0,0) [/m] returns without doing anything.
Just like [m] MERGESORT(A,1,1) [/m], [m] MERGESORT(A,2,2) [/m], and [m] MERGESORT(A,3,3) [/m].

And after those, MERGE will be called. (Thinking)

 

[evinda]

That's quite a complicated algorithm! (Sweating)

Well, it may suffice that it merges 2 sorted arrays into a new array, that is then sorted. (Whew)
Well, [m] MERGESORT(A,0,0) [/m] returns without doing anything.
Just like [m] MERGESORT(A,1,1) [/m], [m] MERGESORT(A,2,2) [/m], and [m] MERGESORT(A,3,3) [/m].

And after those, MERGE will be called. (Thinking)

What is then the function of [m] MERGESORT [/m] ? (Worried)
I haven't understood how we merge like that two sorted arrays?

 

[I like Serena]

What is then the function of [m] MERGESORT [/m] ? (Worried)
I haven't understood how we merge like that two sorted arrays?

Suppose we have the array L=(4,7,5,9,1,3,2,8).
Then first we sort L1=(4,7,5,9) and L2=(1,3,2,8).
Without going into the details, that will come out as S1=(4,5,7,9) respectively S2=(1,2,3,8).
Then we merge them while keeping the result sorted. (Thinking)

That is, we go through them entry by entry, each time selecting the smallest from both arrays.
First is 1 from S2, followed by 2 and 3 that also come from S2.
That gives us S=(1,2,3).
Then we continue with 4 from S1, so we get S=(1,2,3,4).
And we keep going until we have S=(1,2,3,4,5,7,8,9). (Nerd)