# MergeSort - A Linked Lists Solution

```#include < stdio.h >
#include < stdlib.h >
#include < iostream.h >
#include < string.h >

double objectValue(void *obj) {  return (double)*(int *)obj;  }

class Cell
{
private:
void *object;
Cell *left;
Cell *right;
double (* valfn)(void *);

public:
Cell (void *obj, Cell *lf, Cell *rt, double (* f)(void *))
{  object=obj;  left=lf;  right=rt;  valfn = f;  }
double value()   { return (valfn)(object); }
void *objectOf() { return object; }
Cell *leftOf()   { return left; }
Cell *rightOf()  { return right; }
void  setLeft(Cell *lf)  { left = lf; }
void  setRight(Cell *rt) { right = rt; }
};

/***----------------------------------------------------------------
Merge:
Input: Two linked lists ll, rl, of increasing values
Output: A single linked list of increasing values taken from
ll, rl.  The list is linked on Cell left
--------------------------------------------------------------------***/
Cell *merge(Cell *ll, Cell *rl)
{
Cell *first = NULL, *last = NULL;

while (ll != NULL || rl != NULL)
{
if (ll==NULL || (ll != NULL && rl != NULL && ll->value() > rl->value()))
{
if (first == NULL) first = rl; else last->setLeft(rl);
last = rl;
rl = rl->leftOf();
}
else
{
if (first == NULL) first = ll; else last->setLeft(ll);
last = ll;
ll = ll->leftOf();
}
last->setLeft(NULL);
}
return first;
}

/***--------------------------------------------------------------
MergeSort:
Input: A tree linked on Cell left and right, value cells
are on the bottom level
Output: A linked list, in increasing order, of objects in
the input tree.  List is linked on Cell left
------------------------------------------------------------------***/
Cell *mergeSort(Cell *c)
{
if (c == NULL) return NULL;
if (c->leftOf() == NULL) return c;
return merge(mergeSort(c->leftOf()), mergeSort(c->rightOf()));
}

/***----------------------------------------------------------------
buildTree:
Input: A number d
Output: A complete binary tree of depth d with number at
the bottom level.  This is only for the convenience
of building a collection of elements to merge
--------------------------------------------------------------------***/
Cell *buildTree(int d)
{
if (d == 0) return new Cell(new int(rand()/100), NULL, NULL, objectValue);
return new Cell(NULL, buildTree(d-1), buildTree(d-1), objectValue);
}

void showList(Cell *c)
{
cout << ">>> Showing List:\n  ";
for (Cell *p=c ; p!= NULL ; p=p->leftOf())
cout << p->value() << " ";
cout << "\n";
}

void main()
{
showList(mergeSort(buildTree(5)));
}
```