Google Answers Logo
View Question
Q: C C++ Merge Sort a Linked List problem... ( Answered 5 out of 5 stars,   0 Comments )
Subject: C C++ Merge Sort a Linked List problem...
Category: Computers > Programming
Asked by: balzack-ga
List Price: $10.00
Posted: 23 Apr 2003 21:58 PDT
Expires: 23 May 2003 21:58 PDT
Question ID: 194643
Hi there-

I am trying to use Merge Sort on a linked list. I have it for the most
part but I need some help debugging my program. It's running, but its
not giving the correct output. Instead it's simply reversing the order
of the linked list, not sorting it in numerical order like it should.

I have a base linked list class which I have created. This works
perfectly and it useful for creating a linked list of different types
of objects. Here is a link to this code, so you can see it and
understand it. It's pretty simple, but since the merge sort I'm trying
to do is being intergrated into the class, I'll let you see what the
class looks like by itself first to get an understanding of it:

The basic linked list version has an Anything class, which you'll see
can be inheritied by any other object and then you can use virtual and
apply_to_all any function you like. Very useful for printing out the
linked list while using different objects' print methods.

Now here is the link to my current linked list source code which
include the Merge Sort in the class and doesn't work:

I may be going about it all wrong, but I am sure the algorithm itself
is correct and I must have made some errors when trying to move it
inside my program. I have gotten most of it from a very reliable
source and compiled it outside of my class and it worked perfectly. In
case you would like to see this in action, (the merge sort algorithm
working perfectly) I've also included a link to that here:

The problem I'm having is trying to integrate the two together,
placing the Merge Sort right in the linked list class. Now when I am
trying to move the Merge Sort in the Linked List I ran into a few
problems. To make it easier to read/write from now on I'll refer to
the basic working Linked List version as BLL and the version thats not
working with Merge Sort as the MS.

First off, you'll notice that in the BLL version, the line of code,
"Link *realdata"
is a protected member, but in the MS version I had to move it to
"public" in order to be able to access the head of the linked list in
the main like this, "mylist.merge_sort( &mylist.realdata );"

I also think that maybe I am comparing the wrong piece of data in my
merge sort comparisons. Just a guess, thats why I'm here for help.

The list is being reversely sorted, not numerically sorted like it's
supposed to be. (it might actually not even be reversely sorted, it
could be a coincidence, i'm not sure) I just know it's not working and
I can't figure out why.

Thanks alot for your help on this one, if you have any
questions/clairification needed, just post and I'll respond very
promptly. Also if I get a good answer I'll leave a nice tip! Thanks
alot for all the help!
Subject: Re: C C++ Merge Sort a Linked List problem...
Answered By: dogbite-ga on 24 Apr 2003 00:03 PDT
Rated:5 out of 5 stars
Hi balzack-ga,

  Okay, I've added merge to your linked list code.

  I'm uploading the code to my server now.  This

   will be active shortly.


Clarification of Answer by dogbite-ga on 24 Apr 2003 00:46 PDT
Hi balzack,

  I'm just confirming that I have uploaded
  the code to my server and the link is
  now active.  The code is commented, but
  please let me know if you have any questions 
  about it.

  Good luck!


Request for Answer Clarification by balzack-ga on 24 Apr 2003 07:37 PDT
Wow, thanks for the quick help. I don't have time at the moment to
take a look, i was just seeing if anyone had further questions. I will
check the code later on today and make sure I have no questions.
Thanks for the quick response.

Clarification of Answer by dogbite-ga on 24 Apr 2003 08:26 PDT
Hi balzack,

  Nope, no questions from this end.
  I'm glad you're happy with the 
  response time.


Request for Answer Clarification by balzack-ga on 24 Apr 2003 23:27 PDT
OK, after looking thru the code I have a few questions, but overall
great job:

int size2 = numberOfElements % 2 ? size1 + 1 : size1;

can you explain what this means? i believe its some kind of and
if/else statement, but i dont know the syntax cause i myself never use
it. if you could convert it to an if/else i'd appreciate it.

also what is the point of adding this to the Integer:public Anything
class?  i realize you're defining the '<' but what does it do exactly?
  bool operator< (Anything &a)
    Integer& i = dynamic_cast<Integer&> (a);
    return value < i.value;

also say i added another class with strings to be added to the linked
list. it would look something like this:
class MyString:public Anything, public string
{ public:
MyString(string & s):string(s) {}
MyString(char  * s):string(s) {}
MyString(void):string() {}
virtual void print(void) {printf(" %s ", this->c_str()); } 

how would i need to change the custom operator to handle that as well?

one last thing. the part where the algorithm is actually comparing the
data...i'm trying to make it easy for me to follow through the
algorithm so i understand it completely, so i'm trying to add a line
cout << "comparing " << ((first -> data)) << " to " << ((mid -> data))
<< endl;
to print out the comparisions of data being made each step along the
way. this prints memory addresses, how can i get it to print out the
actual data?

other than that everything looks great. thanks again for the help.

Clarification of Answer by dogbite-ga on 25 Apr 2003 06:37 PDT
Hi balzack,

  I put a new version of the code here:

  And, let me address your questions one 
  at a time:

    1) "int size2 = numberOfElements % 2 ? size1 + 1 : size1;"
       - you're exactly right -- that is a compact syntax
         for an if/else statement.  i have expanded it
         to a standard if/else block in the new code.

    2) bool operator< (Anything &a)
       - again, you're right -- this is overloading the '<'
         operator.  This is needed because the '<' comparison
         operator will not automatically work on the Anything
         class (or its subtypes).  The function takes in another
         object of its type and returns whether it is 'smaller'
         than the inputed object.

     3) I have included an example MyString class in the
        code.  That class must overload any abstract virtual
        (keyword virtual and assigned to zero in an ancestor)
        functions.  As such, it must overload the operator<.
        It must also overload the toString() function that I
        also added to the new code.

      4) I added a virtual toString() function that returns a
         string holding its value.  I also added a cout 
         statement that prints out the comparisons you want.

    I hope helps clear things up.


Request for Answer Clarification by balzack-ga on 26 Apr 2003 22:34 PDT
OK great, just one last question that I have.

Integer& i = dynamic_cast<Integer&> (a);
MyString& s2 = dynamic_cast<MyString&> (a);

Could you just explain what these two statements are doing?

Thanks alot for the help.

Clarification of Answer by dogbite-ga on 27 Apr 2003 07:27 PDT
Hello balzack-ga,

  The operator< function takes an Anything
  reference because it is overriding the
  virtual operator< function in the parent
  Anything class.  As such, the Anything
  reference needs to be cast into an Integer 
  reference or a MyString reference.

  So the dynamic_cast syntax casts, or names,
  the Anything object to the proper subclass.

  Does that make sense?


Request for Answer Clarification by balzack-ga on 27 Apr 2003 15:21 PDT
OK, that makes sense now but why when you setup:

virtual bool operator< (Anything &i) = 0;

Does it need to be set to zero? (I really think this is the last question =) )

Thanks again for all the help.

Clarification of Answer by dogbite-ga on 27 Apr 2003 15:47 PDT
Hey balzack-ga,

  Yes, you should set it to zero
  in the parent.  That way you force
  all implementing subclasses to 
  implement that function.  Each
  subclass will most likely have a 
  different meaning for "<", so you
  should force them to implement it.

balzack-ga rated this answer:5 out of 5 stars and gave an additional tip of: $2.00
Great job, thanks for all your help. Excellent answer.

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy