Write a natural merge sort code that sorts a chain of elements. 
Should be a member of the class chain:

/** linked implementation of LinearList */

package dataStructures;

import java.util.*;

public class Chain implements LinearList
{
   // data members
   protected ChainNode firstNode;
   protected int size;

   // constructors
   /** create a list that is empty */
   public Chain(int initialCapacity)
   {
    // the default initial values of firstNode and size
    // are null and 0, respectively
   }

   public Chain()
      {this(0);}

   // methods
   /** @return true iff list is empty */
   public boolean isEmpty()
      {return size == 0;}

   /** @return current number of elements in list */
   public int size()
      {return size;}

   /** @throws IndexOutOfBoundsException when
     * index is not between 0 and size - 1 */
   void checkIndex(int index)
   {
      if (index < 0 || index >= size)
         throw new IndexOutOfBoundsException
               ("index = " + index + "  size = " + size);
   }

   /** @return element with specified index
     * @throws IndexOutOfBoundsException when
     * index is not between 0 and size - 1 */
   public Object get(int index)
   {
      checkIndex(index);
   
      // move to desired node
      ChainNode currentNode = firstNode;
      for (int i = 0; i < index; i++)
         currentNode = currentNode.next;
   
      return currentNode.element;
   }

   /** @return index of first occurrence of theElement,
     * return -1 if theElement not in list */
   public int indexOf(Object theElement)
   {
      // search the chain for theElement
      ChainNode currentNode = firstNode;
      int index = 0;  // index of currentNode
      while (currentNode != null &&
            !currentNode.element.equals(theElement))
      {
         // move to next node
         currentNode = currentNode.next;
         index++;
      }
   
      // make sure we found matching element
      if (currentNode == null)
         return -1;
      else
         return index;
   }

   /** Remove the element with specified index.
     * All elements with higher index have their
     * index reduced by 1.
     * @throws IndexOutOfBoundsException when
     * index is not between 0 and size - 1
     * @return removed element */
   public Object remove(int index)
   {
      checkIndex(index);
   
      Object removedElement;
      if (index == 0) // remove first node
      {
         removedElement = firstNode.element;
         firstNode = firstNode.next;
      }
      else 
      {  // use q to get to predecessor of desired node
         ChainNode q = firstNode;
         for (int i = 0; i < index - 1; i++)
            q = q.next;
      
         removedElement = q.next.element;
         q.next = q.next.next; // remove desired node
      }
      size--;
      return removedElement;
   }

   /** Insert an element with specified index.
     * All elements with equal or higher index
     * have their index increased by 1.
     * @throws IndexOutOfBoundsException when
     * index is not between 0 and size */
   public void add(int index, Object theElement)
   {
      if (index < 0 || index > size)
         // invalid list position
         throw new IndexOutOfBoundsException
               ("index = " + index + "  size = " + size);
   
      if (index == 0)
         // insert at front
         firstNode = new ChainNode(theElement, firstNode);
      else
      {   // find predecessor of new element
         ChainNode p = firstNode;
         for (int i = 0; i < index - 1; i++)
            p = p.next;
      
          // insert after p
         p.next = new ChainNode(theElement, p.next);
      }
      size++;
   }

   /** convert to a string */
   public String toString()
   {
      StringBuffer s = new StringBuffer("["); 
   
      // put elements into the buffer
      ChainNode currentNode = firstNode;
      while(currentNode != null)
      {
         if (currentNode.element == null)
            s.append("null, ");
         else
            s.append(currentNode.element.toString() + ", ");
         currentNode = currentNode.next;
      }
      if (size > 0)
         s.delete(s.length() - 2, s.length());  // remove last ", "
      s.append("]");
   
      // create equivalent String
      return new String(s);
   }

   /** create and return an iterator */
   public Iterator iterator()
      {return new ChainIterator();}

   /** chain iterator */
   private class ChainIterator implements Iterator
   {
      // data member
      private ChainNode nextNode;
   
      // constructor
      public ChainIterator()
      {nextNode = firstNode;}
   
      // methods
      /** @return true iff list has a next element */
      public boolean hasNext()
         {return nextNode != null;}
   
      /** @return next element in list
        * @throws NoSuchElementException
        * when there is no next element */
      public Object next()
      {
         if (nextNode != null)
         {
            Object elementToReturn = nextNode.element;
            nextNode = nextNode.next;
            return elementToReturn;
         }
         else
            throw new NoSuchElementException("No next element");
      }
   
      /** unsupported method */
      public void remove()
      {
         throw new UnsupportedOperationException
               ("remove not supported");
      }   
   }

Linearlist code is:

/** interface for linear lists */

   package dataStructures;

   public interface LinearList
   {
      public boolean isEmpty();
      public int size();
      public Object get(int index);
      public int indexOf(Object theElement);
      public Object remove(int index);
      public void add(int index, Object theElement);
      public String toString();
   }
Format should be similar to:
public class ChainWithNaturalMergeSort extends Chain
{
   static ArrayQueue queue = new ArrayQueue(10);
   static int numberOfSegments;

   public ChainWithNaturalMergeSort(int initialCapacity)
   {  super(initialCapacity);}

   public ChainWithNaturalMergeSort()
   {   super();}

   public void naturalMergeSort()   
   {
      Insert code here
   }

---

Request for Question Clarification by rbnn-ga on 04 Aug 2002 16:52 PDT

Hi,

Just a couple of questions for you:

Do you want the class ChainWithNaturalMergeSort to be in the package
datStructures? I would assume so.

Anyway, where I'm confused is in these lines:

   static ArrayQueue queue = new ArrayQueue(10); 
   static int numberOfSegments; 

part of the boilerplate code for ChainWithNaturalMergeSort. I have to
admit I cannot see why the class would need such static variables. For
that matter, ArrayQueue is not a normal java.util class, but it's also
not defined in your code. Can you verify that you intended to include
these lines?

Finally, are you most interested in running speed or in clarity of
code.

---

Clarification of Question by aznmattuf-ga on 04 Aug 2002 16:59 PDT

First:
ArrayQueue class is:

/** a queue class that uses a one-dimensional array */

package dataStructures;

public class ArrayQueue implements Queue
{
   // data members
   int front;          // one counterclockwise from first element
   int rear;           // position of rear element of queue
   Object [] queue;    // element array

   // constructors
   /** create a queue with the given initial capacity */
   public ArrayQueue(int initialCapacity)
   {
      if (initialCapacity < 1)
         throw new IllegalArgumentException
               ("initialCapacity must be >= 1");
      queue = new Object [initialCapacity + 1];
      // default front = rear = 0
   }

   /** create a queue with initial capacity 10 */
   public ArrayQueue()
   {// use default capacity of 10
      this(10);
   }

   // methods
   /** @return true iff queue is empty */
   public boolean isEmpty()
      {return front == rear;}


   /** @return front element of queue
     * @return null if queue is empty */
   public Object getFrontElement()
   {
      if (isEmpty())
         return null;
      else
         return queue[(front + 1) % queue.length];
   }

   /** @return rear element of queue
     * @return null if the queue is empty */
   public Object getRearElement()
   {
      if (isEmpty())
         return null;
      else
         return queue[rear];
   }

   /** insert theElement at the rear of the queue */
   public void put(Object theElement)
   {
      // increase array length if necessary
      if ((rear + 1) % queue.length == front)
      {// double array size
         // allocate a new array
         Object [] newQueue = new Object [2 * queue.length];

         // copy elements into new array
         int start = (front + 1) % queue.length;
         if (start < 2)
            // no wrap around
            System.arraycopy(queue, start, newQueue, 0,
                             queue.length - 1);
         else
         {  // queue wraps around
            System.arraycopy(queue, start, newQueue, 0,
                             queue.length - start);
            System.arraycopy(queue, 0, newQueue,
                             queue.length - start, rear + 1);
         }

         // switch to newQueue and set front and rear
         front = newQueue.length - 1;
         rear = queue.length - 2;   // queue size is queue.length - 1
         queue = newQueue;
      }

      // put theElement at the rear of the queue
      rear = (rear + 1) % queue.length;
      queue[rear] = theElement;
   }

   /** remove an element from the front of the queue
     * @return removed element
     * @return null if the queue is empty */
   public Object remove()
   {
      if (isEmpty())
         return null;
      front = (front + 1) % queue.length;
      Object frontElement = queue[front];
      queue[front] = null;   // enable garbage collection
      return frontElement;
   }
I'm trying to use the array queue to keep track of the segments since
it is a natural merge instead of a normal merge sort

---

Request for Question Clarification by rbnn-ga on 04 Aug 2002 17:05 PDT

Hi again,

One other question for you:

The class Chain uses a class ChainNode which, unfortunately, isn't
defined. Is there supposed to be a definition of ChainNode somewhere?
If so could you post it please? (I'm assuming that the class Chain was
already written, and thus ChainNode as well).

---

Clarification of Question by aznmattuf-ga on 04 Aug 2002 17:08 PDT

sure, sorry bout that:
class ChainNode code:

/** Node class used by linked structures.
  * This class and its data members are
  * visible only within the package dataStructures. */

package dataStructures;


class ChainNode
{
   // package visible data members
   Object element;
   ChainNode next;

   // package visible constructors
   ChainNode() {}
     
   ChainNode(Object element)
      {this.element = element;}

   ChainNode(Object element, ChainNode next)
      {this.element = element;
       this.next = next;}
}

Thanks for your question.

Merge sort is one of my favorite algorithms, actually; it's the first
sorting algorithm I learned.
It's almost miraculous how simple its expression is:
     sort(list) = 
           if (list has 1 or 0 elements return list)
           else 
               sort(first half of list)
               sort(second half of list)
               merge the results.

There are a number of merge-sort algorithms and demos on the net, one
animation you might enjoy is at:
http://www2.ics.hawaii.edu/~qizhang/ics665/mergesort.html

Anyway, it is remarkable that if you look at the code to this
algorithm, it is hard even to see where it compares elements! Most of
the code just handles trivialities, the comparison is hidden away.

By the way I assume you are familiar with the java "Comparable"
interface. This is interface that objects which can be compared
implement. So, when you sort something, you have to make sure all your
objects implement "Comparable".


By the way, for general coding practice, I recommend the site
http://www.topcoder.com .

It has various programming competitions and it's a good way to learn
Java (or other languages).

OK:

To compile the code, put the ChainWithNaturalMergeSort class source
below in the dataStructures directory, the same directory where Chain
is. The compile it just as you would compile
Chain.java.

I've included a main() method that lets you test the implementation. I
find it's always a good idea to have one of these.

To run the class, from one directory above dataStructures, just type
something like: java dataStructures.ChainWithNaturalMergeSort a b c...

Here are examples of how I ran it:
java dataStructures.ChainWithNaturalMergeSort 
The initial value of the chain is: 
[]
The sorted value of the chain is: 
[]

java dataStructures.ChainWithNaturalMergeSort one-element
The initial value of the chain is: 
[one-element]
The sorted value of the chain is: 
[one-element]

java dataStructures.ChainWithNaturalMergeSort one-element two-element
The initial value of the chain is: 
[one-element, two-element]
The sorted value of the chain is: 
[one-element, two-element]

java dataStructures.ChainWithNaturalMergeSort two-element one-element
The initial value of the chain is: 
[two-element, one-element]
The sorted value of the chain is: 
[one-element, two-element]

java dataStructures.ChainWithNaturalMergeSort p q r s t u v f g h i j
k l m n o  w x y z a b c d e
The initial value of the chain is: 
[p, q, r, s, t, u, v, f, g, h, i, j, k, l, m, n, o, w, x, y, z, a, b,
c, d, e]
The sorted value of the chain is: 
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w,
x, y, z]

Feel free to ask any questions and good luck.


package dataStructures;
import java.util.Iterator;

public class ChainWithNaturalMergeSort extends Chain 
{ 
 
    //constructors
   public ChainWithNaturalMergeSort(int initialCapacity) 
   {  super(initialCapacity);} 
 
   public ChainWithNaturalMergeSort() 
   {   super();} 
 
    //methods 
    /** Sort the list according to the natural order of its elements.
Each element must implement the Comparator interface.
        This uses a merges sort algorithm
    */

   public void naturalMergeSort()    
   { 
       int nelements=size();   // number of elements
       if (nelements==0||nelements==1)return; // Already sorted

       Comparable[] array=new Comparable[nelements]; //first we get
everything into an array,
                                                     //since these are
a bit more efficient and easier to work with
       Iterator iter= iterator();                    //Iterate through
each element of the Chain

       for (int i=0;i<nelements;++i)                 // Set the value
of the i'th array element to the i'th element in the chain.
	   array[i]=(Comparable)(iter.next());  //Note that this will give a
"class cast exception" if the elements are not Comparables.
       sort(array);                             //merge sort the value

       ChainNode current=firstNode;             //and set each element
in the chain to the sorted value.
 
       for (int i=0;i<nelements;++i){
	   current.element=array[i];
	   current=current.next;
       }
   }

    //This is the routine that actually does the work. It takes an
array of Comparables and sorts it using merge sort.

    void sort(Comparable[] array){
	int nelements=array.length;
	if (nelements<=1)return;                     // already sorted
	int midpoint=nelements/2;                    // get the first half
	Comparable[] array1=new Comparable[midpoint]; // we partition the
array
	Comparable[] array2=new Comparable[nelements-midpoint]; 

	System.arraycopy(array,0,array1,0,array1.length);  // set up the
first array
	System.arraycopy(array,array1.length,array2,0,array2.length); //set
up the second array
	sort(array1);  //recursively sort the first array
	sort(array2);  //recursively sort the second array

	//The following line simply merges the sorted arrays we've made, and
then copies the result back to the original array.
	System.arraycopy(merge(array1,array2),   
			 0,
			 array,
			 0,
			 nelements);
			 
    }

    //This function takes two sorted arrays as input and returns the
sorted array that has all the elements of each array

    Comparable[] merge(Comparable[] array1, Comparable[] array2){
	Comparable[] result=new Comparable[array1.length+array2.length];
//will hold the result
	int nextinsert=0; // next element of result to set
	int nextarray1element=0; // next element of array1 to check
	int nextarray2element=0; // next element of array2 to check
	
	while(nextinsert<result.length){  //while there are still more
elements
	    if (nextarray1element>=array1.length)  // have we finished
array1? if so, add an array2 element
		result[nextinsert++]=array2[nextarray2element++];
	    else if (nextarray2element>=array2.length) //similarly for array2
		result[nextinsert++]=array1[nextarray1element++];

	    //The following line is the only place in the whole class we
actually compare anything!!
            //we see if the next array1 element is smaller than or
equal to according to the natural order to the next array2 element,
            // and if so we add it to the result.
	    //Because we use "<=0" not "<0" this is a  "stable sort" which
means it doesn't change the order of equal elements in the input.

	    else if (array1[nextarray1element].compareTo(array2[nextarray2element])<=0)
		result[nextinsert++]=array1[nextarray1element++];
	    else 
		result[nextinsert++]=array2[nextarray2element++];
	}
	return result;  
    }


    //The next routine is simply used for testing. To test, just call
the function main with arguments the strings to be sorted.

    public static void main(String[]argv){
	ChainWithNaturalMergeSort chain=new ChainWithNaturalMergeSort();
	for (int i=0;i<argv.length;++i)
	    chain.add(i,argv[i]);
	System.out.println("The initial value of the chain is: \n"+chain);
	chain.naturalMergeSort();
	System.out.println("The sorted value of the chain is: \n"+chain);
    }
}

---

Request for Answer Clarification by aznmattuf-ga on 04 Aug 2002 18:59 PDT

Thanks for the answer, however, the natural merge sort is what i'm
looking for.  The natural merge sort looks for elements through the
chain that are already in order, and uses those "segments" to merge
upon one another.  I.E.
if the original chain is: 6,2,1,2,3,68,65,44,45,46,47,8,5,10,3,6
Then the first run will look like: 
 6 -- 2 -- 1,2,3,68 -- 65 -- 44,45,46,47 - 8 - 5,10 -- 3,6 with 8
segments
The program would then merge 6 and 2 to yield
2,6 -- 1,2,3,68 -- 65-- 44,45,46,47 - 8 - 5,10 -- 3,6 with 7 segments
then it merges (1,2,3,68) and 65 to yield 
2,6, -- 1,2,3,65,68 -- 44,45,46,47 -- 8 -- 5,10 -- 3,6 with 6 segments
then merges (44,45,46,47) and 8 to yield
2,6 -- 1,2,3,65,68 -- 8,44,45,46,47 -- 5,10 -- 3,6 with 5 segments
then merges 5,10 with 3, 6 to yield
2,6 -- 1,2,3,65,68 -- 8,44,45,46,47 -- 3,5,6,10 with 4 segments
then merges 2,6 with 1,2,3,65,68 to yield
1,2,2,3,6,65,68 -- 8,44,45,46,47 -- 3,5,6,10 with 3 segments
then merges 8,44,45,46,47 with 3,5,6,10 to yield
1,2,2,3,6,65,68 -- 3,5,6,10,44,45,46,47 with 2 segments
and finally merge those two
to get 1,2,2,3,3,6,8,10,44,45,46,47,65,68 consisting of one segment
I have a similar code for this "Natural" merge sort but not for
chains, if you could help construct the code based on how the example
is run, that would be very appreciated.  I already have the coding for
a regular merge sort based on size.  Thank you

---

Request for Answer Clarification by aznmattuf-ga on 04 Aug 2002 19:02 PDT

Here's what i have for a natural merge sort, however, I'm trying to
code it using ChainNodes.  here's the regular class:
public class NaturalMergeSort
{
   // define a queue used for the start positions of sorted segments
   static ArrayQueue queue = new ArrayQueue(10);
   static int numberOfSegments;

   /** sort the elements a[0 : a.length - 1] using
     * the natural merge sort method */
   public static void naturalMergeSort(Comparable [] a)
   {
      if (a.length <= 1)
         // already sorted
         return;

      // define an auxiliary array to faciltate merging
      Comparable [] b = new Comparable [a.length];

      // find the natural segments and save their start positions in a
queue
      queue.put(new Integer(0));  // first segment starts at 0
      numberOfSegments = 1;
      for (int i = 1; i < a.length; i++)
         if (a[i - 1].compareTo(a[i]) > 0)
         {// a new segment starts at i
            numberOfSegments++;
            queue.put(new Integer(i));
         }

      while (numberOfSegments > 1)
      {// numberOfSegments is updated by naturalMergePass
         naturalMergePass(a, b); // merge from a to b
         naturalMergePass(b, a); // merge from b to a
      }
   }

   /** merge pairs of adjacent segments from x to y*/
   public static void naturalMergePass(Comparable [] x, Comparable []
y)
   {
      for (int i = 1; i < numberOfSegments; i += 2)
      {// merge two segments
         // find the start and end of the two segments
         Object a = queue.remove();
         int startA = ((Integer) a).intValue();
         int startB = ((Integer) queue.remove()).intValue();
         Object z = queue.getFrontElement();
         int endB = (z == null || ((Integer) z).intValue() == 0) ?
                       x.length - 1 : ((Integer) z).intValue() - 1;
         // merge them 
         merge(x, y, startA, startB - 1, endB);

         // put segment start on queue
         queue.put(a);
      }
   
      // one segment may remain
      if (numberOfSegments % 2 == 1)
      {// copy last segment to y
         Object a = queue.remove();
         int startA = ((Integer) a).intValue();
         for (int i = startA; i < x.length; i++)
            y[i] = x[i];
         queue.put(a);
      }

      // update number of segments
      if (numberOfSegments % 2 == 1)
         numberOfSegments = numberOfSegments / 2 + 1;
      else
         numberOfSegments /= 2;
   }
   
   /** merge c[l:m] and c[m + 1:r] to d[l:r] */
   public static void merge(Comparable [] c, Comparable [] d,
                            int l, int m, int r)
   {
      int i = l,      // cursor for first segment
          j = m + 1,  // cursor for second
          k = l;      // cursor for result
   
      // merge until i or j exits its segment
      while ((i <= m) && (j <= r))
         if (c[i].compareTo(c[j]) <= 0)
            d[k++] = c[i++];
         else
            d[k++] = c[j++];
   
      // take care of left overs
      if (i > m)
         for (int q = j; q <= r; q++)
             d[k++] = c[q];
      else
         for (int q = i; q <= m; q++)
             d[k++] = c[q];
   }
}

---

Request for Answer Clarification by aznmattuf-ga on 04 Aug 2002 19:03 PDT

the above code has not been designed to run with Chain thats what i'm
working on how to code it so it uses ChainNodes

---

Clarification of Answer by rbnn-ga on 04 Aug 2002 23:56 PDT

OK, I'm including the code for the ChainWithNaturalMergeSort below.

It can be run in two modes, by setting the variable Debug to "false"
or "true".

If you set it to true, it will print out the segments that are
computed, so that you can verify it is a
natural merge sort.

Some brief notes on the design:
I tried to follow reasonably closely the array code you gave. However,
the queue variable is not
static; it was only static in the array code because there was no
class to be acted upon.
In this case the queue is simply a private instance variable.

I did not use separate x and y variables to do the copying, as this
seemed like some unnecessary work in the
case of Lists.

I haven't put too much in the way of comments here, as I am not sure
exactly what you are looking for, but of course I would
be happy to answer any questions on the code.

Here are some scripts:

/cygdrive/c/stiller/google: java
dataStructures.ChainWithNaturalMergeSort
unsorted is: []
sorted is: []
/cygdrive/c/stiller/google: java
dataStructures.ChainWithNaturalMergeSort zzz
unsorted is: [zzz]
sorted is: [zzz]
/cygdrive/c/stiller/google: java
dataStructures.ChainWithNaturalMergeSort zzz aaa
unsorted is: [zzz, aaa]
sorted is: [aaa, zzz]
/cygdrive/c/stiller/google: java
dataStructures.ChainWithNaturalMergeSort aaa zzz
unsorted is: [aaa, zzz]
sorted is: [aaa, zzz]
/cygdrive/c/stiller/google: java
dataStructures.ChainWithNaturalMergeSort a b c
unsorted is: [a, b, c]
sorted is: [a, b, c]
/cygdrive/c/stiller/google: java
dataStructures.ChainWithNaturalMergeSort c b a
unsorted is: [c, b, a]
sorted is: [a, b, c]
/cygdrive/c/stiller/google: java
dataStructures.ChainWithNaturalMergeSort c a b
unsorted is: [c, a, b]
sorted is: [a, b, c]
/cygdrive/c/stiller/google: java
dataStructures.ChainWithNaturalMergeSort b a c
unsorted is: [b, a, c]
sorted is: [a, b, c]
/cygdrive/c/stiller/google: java
dataStructures.ChainWithNaturalMergeSort o p q r  d e f g h i s t u v
w x y z j  a b c k l  m n
unsorted is: [o, p, q, r, d, e, f, g, h, i, s, t, u, v, w, x, y, z, j,
a, b, c, k, l, m, n]
sorted is: [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s,
t, u, v, w, x, y, z]
/cygdrive/c/stiller/google: # Now with the Debug switch set to on....
/cygdrive/c/stiller/google: java
dataStructures.ChainWithNaturalMergeSort o p q r  d e f g h i s t u v
w x y z j  a b c k l  m n
unsorted is: [o, p, q, r, d, e, f, g, h, i, s, t, u, v, w, x, y, z, j,
a, b, c, k, l, m, n]
Showing segments: 
Segment 0 is: [o p q r ]
Segment 1 is: [d e f g h i s t u v w x y z ]
Segment 2 is: [j ]
Segment 3 is: [a b c k l m n ]
Showing segments: 
Segment 0 is: [d e f g h i o p q r s t u v w x y z ]
Segment 1 is: [a b c j k l m n ]
Showing segments: 
Segment 0 is: [a b c d e f g h i j k l m n o p q r s t u v w x y z ]
sorted is: [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s,
t, u, v, w, x, y, z]
/cygdrive/c/stiller/google: 

package dataStructures;
import java.util.Iterator;

public class ChainWithNaturalMergeSort extends Chain 
{ 
    private ArrayQueue queue;
    private int numberSegments;
    public static final boolean Debug=false;
    //constructors
   public ChainWithNaturalMergeSort(int initialCapacity) 
   {  super(initialCapacity);} 
 
   public ChainWithNaturalMergeSort() 
   {   super();} 
 
   public void naturalMergeSort()    
   { 
       int nelements=size();   // number of elements
       if (nelements==0||nelements==1)return; // Already sorted
       queue=new ArrayQueue(10);
       numberSegments=0;
       queue.put(firstNode);
       ChainNode current=firstNode;
       while(true){
	   ChainNode previous=current;
	   current=current.next;
	   if (current==null){queue.put(current);++numberSegments;break;}
	   if (((Comparable)(current.element)).compareTo(previous.element)<0){
	       queue.put(current);
	       numberSegments++;
	   }
       }

       while(numberSegments>1){
	   showSegments();
	   naturalMergePass();
       }
       showSegments();
   }

    public void naturalMergePass(){
	Object start=queue.getFrontElement();
	while(true){
	    ChainNode a =(ChainNode)(queue.remove());
	    if (a==null){queue.put(a);break;}
	    ChainNode b=(ChainNode)(queue.remove());
	    if (b==null){queue.put(a);queue.put(b);break;}
	    ChainNode z=(ChainNode)(queue.getFrontElement());
	    merge(a,b,z);
	    queue.put(a);
	    numberSegments--;
	}
    }


    public void merge(ChainNode start1,ChainNode start2, ChainNode
end){
	ChainNode next1=start1;
	ChainNode next2=start2;
	ChainNode previous=null;
	ChainNode first=null;
	int iternumber=0;
	while(next1!=start2 || next2!=end){
	    ChainNode current=new ChainNode();
	    if (previous!=null)
		previous.next=current;
	    else 
		first=current;
	    
	    previous=current;
	    if (next1==start2){
		current.element=next2.element;
		next2=next2.next;
	    }
	    else if (next2==end){
		current.element=next1.element;
		next1=next1.next;
	    }
	    else if (((Comparable)(next1.element)).compareTo(next2.element)<=0)
		{current.element=next1.element;next1=next1.next;}
	    else
		{current.element=next2.element;next2=next2.next;}
	}
	ChainNode next=start1;
	while(next!=end){
	    next.element=first.element;
	    first=first.next;
	    next=next.next;}
	
   }
    public static void main(String[]argv){
	ChainWithNaturalMergeSort chain=new ChainWithNaturalMergeSort();
	for (int i=0;i<argv.length;++i)
	    chain.add(i,argv[i]);
	System.out.println("unsorted is: "+chain);
	chain.naturalMergeSort();
	System.out.println("sorted is: "+chain);
    }
    public String showQueue(ArrayQueue q){
	java.util.ArrayList foo=new java.util.ArrayList();
	String result="";
	while (!q.isEmpty()) foo.add(q.remove());
	for (int i=0;i<foo.size();++i){
	    result+=foo.get(i)+ " ";
	    q.put(foo.get(i));
	}
	return result;
    }
	    
    public void showSegments(){
	if (Debug)System.out.println("Showing segments: ");
	if (!Debug)return;
	java.util.ArrayList foo=new java.util.ArrayList();
	while (!queue.isEmpty()) foo.add(queue.remove());
	for (int i=0;i<foo.size()-1;++i){
	    ChainNode start= (ChainNode)(foo.get(i));
	    System.out.print("Segment " +i+ " is: ");
	    System.out.print("[");
	    ChainNode current=start;
	    do{
		System.out.print(current.element+" ");
		current=current.next;
	    }
	    while(current!=foo.get(i+1));
	    System.out.println("]");
	}
	for (int i=0;i<foo.size();++i) queue.put(foo.get(i));
    }
		
	

}

---

Request for Answer Clarification by aznmattuf-ga on 05 Aug 2002 15:01 PDT

i posted a possible approach, I was wondering if you thought of either
your own way or if this could work.  The null pointers are a problem
for me

---

Clarification of Answer by rbnn-ga on 05 Aug 2002 17:59 PDT

I'm happy to help with the request for clarification.

To answer your question about where my original code came from, I just
modified the existing code you gave me for NaturalMergeSort on arrays
to work with lists; I just changed "indices" in the array to
"ChainNodes".

Now, you posted some new code and if I understand you correctly you
are curious why your new code gives a NullPointerException, and also
possibly some suggestions/comments on the code.

Well, the simple answer is that your code gives a NullPointerException
because in the lines:

          // Traverse the chain, place segments into queue       
      while (a != null) 

I think you mean (c!=null) here , not (a!=null) . This is because you
later call on "c.element" and c could be null here.

One *very* good idea in your code is to destructively modify the
ChainNode next pointers so that the segments are actually stored
naturally as null-terminated lists. This dramatically simplifies
everything, I wish
I'd used that idea, since in my original code I kept having to do a
lot of useless and
error-prone bounds-checking.

Anyway, even after fixing the (a!=null) to c!=null there were a few
minor issues in your code, which I took the liberty of correcting
below.

For instance, it's not a good idea for the numberOfSegments variables
to be static ! In java, this means that their value is the same for
all instances of a class, so that if two clients tried to sort two
different ChainWithNaturalMergeSort instances at the same time, they
would get garbage results. (actually you don't really need any static
methods except for main in the class; it's very common among C/C++
programmers when they switch to java to make too many things static.

So I changed out some of the static declarations to instance ones.

Finally, I changed a couple places were you used iteration to loop
over the linked list to recursion.

I did this in two places.

First, when naturalMergeSort first sets up the queue, you can see I
use a different helper function, setupQueue, that uses recursion.

Second, in the merge function, I use a recursive idea (which is MUCH
simpler thanks to the way segments are true chains terminated by
null).

Often, when dealing with linked lists and so on, it's 
simpler to use recursion, not iteration.  True, it can sometimes
be a bit faster to use iteration, but I don't think that's an issue
here.  Anyway, you will see that the recursive solution is much, much
shorter than the iterative one [80 lines versus 180 lines]; it's
easier to debug; and it ran right
the first time with no NullPointerExceptions, which wouldn't have been
the case with an iterative solution. 

Please feel free to continue to ask for more clarifications. 

package dataStructures; 
 
import java.util.*; 
 
public class ChainWithNaturalMergeSort extends Chain 
{ 
    ArrayQueue queue = new ArrayQueue(10); 
    int numberOfSegments; 
 
   public ChainWithNaturalMergeSort(int initialCapacity) 
   { 
      super (initialCapacity); 
   } 
 
   public ChainWithNaturalMergeSort() 
   {  
      super(); 
   } 
 
    void setupQueue(ChainNode a){
	if (a==null) return;
	queue.put(a);
	++numberOfSegments;
	ChainNode next=a.next;
	while(true){
	    if (a.next==null)return;
	    if ((((Comparable)(a.next.element)).compareTo(a.element))<0){
		setupQueue(a.next);
		a.next=null;
		return;
	    }
	    a=a.next;}
    }

   public void naturalMergeSort() 
   { 
      firstNode = naturalMergeSort(firstNode, size);     
   } 
 
    ChainNode naturalMergeSort(ChainNode a, int chainLength) 
   { 
      if (chainLength < 2)  
         return a; 
      setupQueue(a);

    while(numberOfSegments>1)
      { 
         ChainNode mergePrev = ((ChainNode)queue.remove());          
// gets first chain of queue
         ChainNode mergeNext = ((ChainNode)queue.remove());          
// gets second chain off of queue
         a = merge(mergePrev, mergeNext);      // create chain 
         numberOfSegments--; 
         queue.put(a); 
      } 
    return (ChainNode)queue.remove();
   }   

    ChainNode merge(ChainNode e, ChainNode f) 
    { 
         //if one chain is empty, return other chain 
	if (e==null)return f;
	if (f==null)return e;
	if (((Comparable)(e.element)).compareTo(f.element)<=0){
	   e.next=merge(e.next,f);
	   return e;}
       else
	   return new ChainNode(f.element,
				merge(e,f.next));
    }
 
    
 
   public static void main(String[] args) 
   { 
      ChainWithNaturalMergeSort x = new ChainWithNaturalMergeSort(); 
      for (int i=0;i<args.length;++i)x.add(i,args[i]);
      System.out.println("Start x is: "+x);
      x.naturalMergeSort(); 
      System.out.println("end x is: "+x);
   } 
}

Good job, immediate response initially.  Even though question was
initially misinterpreted.  The response afterwards was quick as well. 
Collaborated well with what I had given as input.  Results proved to
be very helpful, many thanks.

Oops! I'm sorry about that. I did indeed misread your question - I
thought "natural merge sort" meant "merge sort under the natural Java
ordering".

Let me think about the actual question you asked for a moment!

this doesn't work, however, its an idea I had:
package dataStructures;

import java.util.*;
import utilities.*;
import wrappers.*;

public class ChainWithNaturalMergeSort extends Chain
{
   static ArrayQueue queue = new ArrayQueue(10);
   static int numberOfSegments;

   public ChainWithNaturalMergeSort(int initialCapacity)
   {
      super (initialCapacity);
   }

   public ChainWithNaturalMergeSort()
   { 
      super();
   }

   public void naturalMergeSort()
   {
      firstNode = naturalMergeSort(firstNode, size);    
   }

   static ChainNode naturalMergeSort(ChainNode a, int chainLength)
   {
      if (chainLength < 2) 
         return a;
      ChainNode b = a;                  // previous
      ChainNode c = a.next;             // currentNode      
      ChainNode mergePrev, mergeNext;   // chains to merge
         
       
          // Traverse the chain, place segments into queue      
      while (a != null)
      {
         if (((Comparable) b.element).compareTo(c.element) > 0)
         {
             numberOfSegments++;        // Segment exists
             b.next = null;             // isolate chain segment 
             queue.put(b);              // place segment in queue
             b = null;
             b = a.next;
             a = a.next;                       
             c = c.next;                // move current node to next
node
         }         
         else
         {               
             a = a.next;
             b.next = a;
             b = b.next;
          //   b.next = c;               //Next node is greater in
value
          //   b = b.next;               //continue adding to segment
             c = c.next;               // move current node to next
node
         }                                         
      }          
            // Check end of chain          
      if (((Comparable)b.element).compareTo(c.element) > 0)
      {   
         numberOfSegments += 2;        // add on last 2 segments
         b.next = null;                // close off segment
         queue.put(b);                 // place segment in queue 
         queue.put(c);                 // place last segment in queue
      }
      else
      {       
         numberOfSegments++;            // only one segment to add
         b.next = c;                   
         b = b.next;                   // close off segment
         queue.put(b);                 // place segment in arrayQueue
      }         
   
             
              
      for (int i = 1; i < numberOfSegments; i++)
      {
         mergePrev = ((ChainNode)queue.remove());           // gets
first chain of queue
         mergeNext = ((ChainNode)queue.remove());           // gets
second chain off of queue
         a = merge(mergePrev, mergeNext);      // create chain
         numberOfSegments--;
         queue.put(a);
      }
          
      return a;                                //return final sorted
chain
   }  
   static ChainNode merge(ChainNode e, ChainNode f)
   {
         //if one chain is empty, return other chain
      if (e == null)
      {
         return f;
      }
      if (f == null)
      {
          return e;
      }
      ChainNode first;                     // first node off of queue
      ChainNode second;                    // second node off of queue
            //test if first segment is smaller than second segment
            // if so, then chain starts at smaller segment, otherwise
            // chain starts at chain b
      if (((Comparable)e.element).compareTo(f.element) < 0)
      {
         first = second = e;
         e = e.next;
      }
      else 
      {
         first = second = f;
         f = f.next;
      }
           // attach remaining nodes in sorted order 
      while (e != null && f != null)
      {
         if (((Comparable)e.element).compareTo(f.element) < 0)
         {
             second.next = e;
             e = e.next;
         }
         else
         {
            second.next = f;
            second = f;
            f = f.next;
         }
         // if one of the nodes has been exhausted
         if (e!= null)
            second.next = e;                  // a is not empty
         else
            second.next = f;                  // b is not empty
      }
         // return sorted chain     
      return first;
     
   } 

   

   public void output()
   {
      System.out.println("***************************************");
      System.out.println("merging: ");
      System.out.println("Chain: ");
      System.out.println(numberOfSegments + " segments");
   }

      
   
            
   public static void main(String[] args)
   {
      ChainWithNaturalMergeSort x = new ChainWithNaturalMergeSort();

      x.add(0, new Integer(6));
      x.add(0,new Integer(3));
      x.add(0, new Integer(10));
      x.add(0, new Integer(5));
      x.add(0,new Integer(8));
      x.add(0,new Integer(47));
      x.add(0,new Integer(46));
      x.add(0,new Integer(45));
      x.add(0,new Integer(44));
      x.add(0,new Integer(65));
      x.add(0,new Integer(68));
      x.add(0,new Integer(3));
      x.add(0,new Integer(2));
      x.add(0,new Integer(1));
      x.add(0,new Integer(2));
      x.add(0,new Integer(6));

      x.naturalMergeSort();
   }
}