Output Problem,

[Waqar Ahmed]

List List:: mergesort(List m)
{
	if(m.count() <= 1)
      return m;
   else
   {
   	List l,r;
      node* temp = m.head;
      node* ptemp = m.head;
      node* first = m.head;
      int c = m.count();
      for(int i = 1; temp->next!=NULL && i<=(c/2)+1; i++)
      	{
         ptemp = temp;
         temp = temp->next;
         }

      ptemp->next = NULL;

      while(first!=NULL)
      {
         l.insert(first->data);
         first = first->next;
      }

      while(temp!=NULL)
      {
      	r.insert(temp->data);
         temp = temp->next;
      }

      cout<<"\t\t";
      l.display(); cout<<"  ";
      if(r.count() == 1) { r.display();}
      cout<<"\t\t";r.display();cout<<"\n";

      l = mergesort(l);
      r = mergesort(r);
   }
}

For example I input this List : 5 3 7 14 2

Desired Output :-

                  5 3 7 14 2

         5 3 7                  14 2

      5 3      7              14     2

    5     3     7           14         2

what I get is :

                  5 3 7 14 2

         5 3 7                  14 2

         5 3                    7             

         5                      3
         14                     2    

What should I do? I have tried every possible thing, but can't even get close.
Can Any body help, please?

[hamsterman]

Do you see what is happening?
As simple recursion could be called "depth first" the function calls happen in the following order

sort(5 3 7 14 2)
sort(5 3 7)
sort(5 3)
sort(14 2)

And that is the order in which lines are printed.
You need, in some way, to undermine this order and instead have

    sort(5 3 7 14 2)
sort(5 3 7)
                 sort(14 2)
sort(5 3)

I suggest that you separate sorting and printing. Instead, while sorting, collect the lists you want in a tree. Later print that. It should be possible to combine the two into one algorithm, but all that would do is make a mess. Even printing a binary tree like this is not trivial.

Ask if you need help with collecting or printing.

[Waqar Ahmed]

Sir,
I am sure you are very right in your opinion. But I haven't yet studied trees.

I have made some alterations, so now the recursive call is like this:

mergesort(List m,List t)
{
.
.
.
m.mergesort(mergesort(l,l),mergesort(r,r));

List t isn't doing anything.

The output has become :-

             5 3 7 14 2

         5 3 7                  14 2

        14                       2 

        5 3                    7             

         5                      3

[hamsterman]

That's a bit of a problem that you don't know trees. More because you must be very new to this than because you need them.

Are you aware that a recursive function can be rewritten as a non recursive one using a list? Example

int fib(int x) {
   if (x < 2) return 1;
   else return fib(x-2) + fib(x-1);
}

can be written as

int fib(int x) {
   stack<int>  indices;
   indices.push(x);
   int result = 0;
   while(!indices.empty()) {
      int n = indices.top();
      indices.pop();
      if (n < 2) result += 1;
      else {
         indices.push(x-1);
         indices.push(x-2);
      }
   }
   return result;
}

If you do this, you can manipulate in what order the functions are called. If you read from top and push on top, you'll have the order you had (this is a lot like how recursion works), however, if you read from top and push to bottom, the order you get is

sort(5 3 7 14 2)
sort(5 3 7)
sort(14 2)
sort(5 3)
sort(7)
sort(14)
sort(2)
sort(5)
sort(3)

and that is a big improvement. This method does require some change for all of the code though.

I noticed that your merge sort doesn't do any merging and doesn't return anything. I suggest that you figure out the algorithm, before trying to enhance it.

[Waqar Ahmed]

I didn't quite understand what you wrote above.

First I change all recursive functions to iterative.
Then how do I get to control the order of functions called?
Am i gonna need queues? thats what I think...

[hamsterman]

Normally recursive calls are sort of in a stack. If you put them in a queue, the order of their executions sort of changes direction, in the right way. Notice that stack and queue are special kinds of lists, hence I didn't name them like that.

I now see another option. Besides the sorted list, sort() would return a list of lines in the tree you want. Example:

sort(1 2 3) returns the first line of "1 2 3" and then the combined results of sort(1 2) and sort(3).
If sort(1 2) returned (by induction)
" 1 2 "
"1   2"
and sort(3) returned "3" then their combination is
" 1 2      3"
"1   2"
and thus sort(1 2 3) returns
"    1 2 3"
" 1 2      3"
"1   2"

Although printing things into strings might too be something you haven't learned yet.

[Waqar Ahmed]

sprintf() function??

[hamsterman]

That works, though I imagine you'll be using something as char[80] for string type which is a bit ugly. Nevertheless it can be done. Was my suggestion clear?

Also, for what purpose are you doing this? Is it a school assignment or your own idea?

[Incis B]

Waqar, It seems as though you may be writing K&R's "C" language. may I ask what compiler you are using?

Too, without a fair to good understanding of "trees" and "recursive functions", you may have difficulties writing & debugging your desired program.

All that aside, I suggest that you first use a pseudo code, ( I use RATFOR; Bell Labs) to design - in a top down modular approach your application - starting from a high level - general design, and work your way towards a detailed design, one from which you can then ( but not before) begin to enter into your IDE for compilation.

If, along the way, you find yourself stuck on one or another subrt'ns, then you have the pseudo code available describing what the subrt'n is suppose to do and how it is suppose to preform and what its arguments are and its return values ( if any) - which can then be posted.

Additionally, a good "up-front', "top-down" design will help with the overall flow and functionality of the application -and will add greatly to the development and debugging progress.
As you may well know - spending 60% of your time in the design phase will reduce your debugging time to 15%. From your existing code, I would venture to say that you may be looking at spending more time fixing your code than you will spend writing it.