Desperatly trying to implement an mergesort algorithm

Desperatly trying to implement an mergesort algorithm

[ejijott]

Hello!

Im having extreme problems trying to implement an mergesort in Ada, and
was hoping from some help in this group :)

My definition of the procedure is this:

type List is array(Natural range <>) of Integer;
.
.
procedure Mergesort(A : in out List);
.
.

And for readability I've used pastebin to host my code
(http://pastebin.com/417262)

I just plain and simply can't grasp what is wrong here! Am I even
partitioning the array properly?

(The merge part isn't complete yet)

Any help is GREATLY appreciated.

Re: Desperatly trying to implement an mergesort algorithm

[Samuel Tardieu]

>>>>> "ejijott" == ejijott  <ejijott@gmail.com> writes:

ejijott> I just plain and simply can't grasp what is wrong here!

This piece seems dubious to me:

                while i <= middle and then j <= A'last loop

I have only had a quick glance at your code, but "or else" would seem
much more logical than "and then" here. You don't want to stop when
one of the boundaries gets reached but when both of them are.

  Sam
-- 
Samuel Tardieu -- sam@rfc1149.net -- http://www.rfc1149.net/sam

Re: Desperatly trying to implement an mergesort algorithm

[ejijott]

Does the partitioning look proper? With me using A'first and A'last?

mergesort(A(A'first .. middle));
mergesort(A(middle+1 .. A'last));

Re: Desperatly trying to implement an mergesort algorithm

[Steve]

<ejijott@gmail.com> wrote in message 
news:1131121827.249591.288510@g14g2000cwa.googlegroups.com...
> Does the partitioning look proper? With me using A'first and A'last?
>
> mergesort(A(A'first .. middle));
> mergesort(A(middle+1 .. A'last));
>

The partitioning looks right to me.

Now a few questions:
  What is left_list for?  (looks like it could be deleted)
  What is right_list for? (looks like it could be deleted)

  In the while loop that does the merging, the smallest value of elements i 
and j are added sortarr, until one of the halves of the sublists is 
exhausted.  What happens to the remaining elements?

That's not your biggest problem:

Hint: If you change the procedure to

procedure Mergesort(A: List) ...

Your code will still compile.

Steve
(The Duck)

Re: Desperatly trying to implement an mergesort algorithm

[Georg Bauhaus]

ejijott@gmail.com wrote:

> I just plain and simply can't grasp what is wrong here! Am I even
> partitioning the array properly?

Could you write your reasoning below every declaration, statement,
and expression in yout program, as a comment?

Also, what text book or reference are you using?