MergeSort Using Linked Lists

(see also the C++ Solution)

import java.io.*;
import java.util.*;

class CellObject
{
   int value() { return 0; }
}

class Int extends CellObject
{
   int number;

   Int(int n) { number = n; }
   int value() { return number; }
}

class Cell
{
   CellObject object;
   Cell left;
   Cell right;

   Cell (CellObject obj, Cell lf, Cell rt) { object=obj; left=lf; right=rt; }
   CellObject objectOf() { return object; }
   Cell  leftOf()   { return left; }
   Cell  rightOf()  { return right; }
   void  setLeft(Cell lf)  { left = lf; }
   void  setRight(Cell rt) { right = rt; }
}

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

      while (ll != null || rl != null)
      {
         if (ll == null ||
             (ll != null && rl != null &&
              ll.objectOf().value() > rl.objectOf().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
   ------------------------------------------------------------------***/
   static 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
   --------------------------------------------------------------------***/
   static Cell buildTree(int d, int e)
   {
      if (d == 0) return new Cell(new Int(e), null, null);
      return
      new Cell(null, buildTree(d-1, (e*233)%100), buildTree(d-1, (e*721)%121));
   }

   static void showList(Cell c)
   {
      System.out.println(">>> Showing List:");
      for (Cell p=c ; p!= null ; p=p.leftOf())
         System.out.print(p.objectOf().value() + " ");
      System.out.println();
   }

   public static void main(String argv[])
   {
      showList(mergeSort(buildTree(5, 161)));
   }
}