Thread: Mergesort with linkedlist using recursion

Hi, I'm trying to do a mergesort with linklist using recursion. The problem I'm running into is, the code will not enter if(ordered[1].size() > 2) if block to process the second part of the linkedlist. I can't seem to figure out why that it. Please look at my code below and let me know if you want me to post the LinkedList class I created, thanks.

mergesort code:

public class Merge{
 
  public static LinkedListABS merge (LinkedListABS first, LinkedListABS second){
    // purpose : to merge together two lists of strings (each that are sorted alphabetically)
    // input : two lists 
    // output : a "new" list that is sorted alphabteically and contains all the elements in the two input lists
    //          the new list should have all new nodes in it
 
    // Note: you must use recursion for this problem
    if(first.look(0).compareTo(second.look(0)) > 0){
      first.insert(second.look(0));
      second.remove();
    } else if(first.look(1).compareTo(second.look(0)) > 0){
      first.insert(second.look(0),1);
    }
 
    return first;
  }
 
 
  public static LinkedListABS[] split(LinkedListABS list){
    // purpose : to split the input list into two (almost) equally sized lists
    // input : a list of strings 
    // output : an array of two "new" lists a list. The first list corresponds to first half of the 
    //          input list and the second list corresponds to the second half of the input list 
    //          The output lists should have all new nodes in it
    // example: list = {s0,s1,s2,s3,s4,s5}
    //          split(list) -> [{s0,s1,s2}, {s3,s4,s5}]
    //          list = {s0,s1,s2,s3,s4,s5,s6}
    //          split(list) -> [{s0,s1,s2,s3}, {s4,s5,6}]
    // when list has even length the list is split exactly in half size()/2 strings in each
    // when list has odd length, then the first list has size()/2+1 strings and the second has size()/2 
    //                                                   (using integer division)
    if(list.size() > 1){
      System.out.println("Entered size>1 and list is: " + list.toString());
      int s = list.size();
      int middle;
      if(s%2 == 0){
        middle = s/2;
      }else{
        middle = (s/2) + 1;
      }
      System.out.println("s = " + s + " middle = " + middle);
      LinkedListABS s1 = CopyLinkedList.copy(list, 0, middle);
      System.out.println("s1 is: " + s1.toString());
      LinkedListABS s2 = CopyLinkedList.copy(list, middle, list.size());
      System.out.println("s2 is: " + s2.toString());
      LinkedListABS[] ordered = {s1,s2};
      System.out.println("ordered[0] is " + ordered[0] + " ordered[1] is " + ordered[1]);
      return ordered;
    }else{
      System.out.println("Entered size <=1");
      LinkedListABS[] ordered = {list};
      System.out.println("ordered is " + ordered[0]);
      return ordered;
    }
 
  }
 
 
  public static LinkedListABS sort(LinkedListABS list){
    // puspose : sorts the link of Strings (alphabteically) using mergesort
    // input : a list of Strings
    // output : a "new" list of the same Strings but sorted alphabetically
    //          (the input list must be left unchanged. the new list must have all new nodes in it)
    System.out.println("entered sort");
    LinkedListABS n = new LinkedList();
 
    LinkedListABS copied = CopyLinkedList.copy(list, 0, list.size());
    System.out.println("copy created: " + copied.toString());
    LinkedListABS[] ordered = split(copied);
    System.out.println("ordered[0] = " + ordered[0].toString() + " ordered[1] = " + ordered[1].toString());
    //if((ordered[0].size() > 2) || (ordered[1].size() > 2)){
    if(ordered[0].size() > 2){
      System.out.println("Entered ordered[0].size() > 2");
      LinkedListABS s = sort(ordered[0]);
      return s;
    } else if(ordered[0].size() == 2){
      System.out.println("Entered ordered[0].size = 2");
      if(ordered[0].look(0).compareTo(ordered[0].look(1)) > 0){
        ordered[0].insert(ordered[0].look(1));
        ordered[0].remove(2);
        System.out.println("ordered[0] = " + ordered[0].toString());
      }
      System.out.println("ordered[0] = " + ordered[0].toString());
    }
 
    if(ordered[1].size() > 2){
      System.out.println("Entered ordered[1].size() > 2");
      LinkedListABS s = sort(ordered[1]);
      return s;
    } else if(ordered[1].size() == 2){
      System.out.println("Entered ordered[1].size = 2");
      if(ordered[0].look(0).compareTo(ordered[0].look(1)) > 0){
        ordered[1].insert(ordered[1].look(1));
        ordered[0].remove(2);
        System.out.println("ordered[1] = " + ordered[1].toString());
      }
      System.out.println("ordered[0] = " + ordered[0].toString());
    }
 
     LinkedListABS m = merge(ordered[0], ordered[1]);
     n = m;
    //}
 
    return n;    
  }
 
}

test code:

public class MergeTest{
 
  public static void main(String[] args){
 
    LinkedListABS list = new LinkedList();
    System.out.println("Size is: " + list.size());
    System.out.println("isEmpty: " + list.isEmpty());
    System.out.println("inserted at: " + list.insert("cat"));
    System.out.println("inserted dog at: " + list.insert("dog"));
    list.insert("eel");
    list.insert("mouse");
    list.insert("goat");
    list.insert("sheep");
    System.out.println("list: " + list.toString());
    LinkedListABS order = Merge.sort(list);
    System.out.println("order is " + order.toString());
    System.out.println("list: " + list.toString());
 
  }
}

--- Update ---

LinkedList class

/
public class LinkedList extends LinkedListABS {
 
  private int position = 1; //variable to hold the position of the node
  private Node runner;
 
  // zero parameter constructor 
  public LinkedList(){
    head = null;
  }
 
  /* checks if list is empty or not 
   * return true if the list is empty and false otherwise*/
  public boolean isEmpty(){
    if(head == null){
      return true;
    }else{
      return false;
    }
  }
 
  /* returns the number of Strings in the list */
  public int size(){
    int s = 0;
    runner = head;
    if(runner == null){
      return 0;
    } else if(runner != null){
      return 1 + tailSize(head.getNode());
    } else{
      return 0;
    }
  }
 
  //to get the size of the tail, helper method for size
  private int tailSize(Node tail){
    if(tail == null){
      return 0;
    }else{
      return 1 + tailSize(tail.getNode());
    }
  }
 
  /* inserts a String s into position pos of the current list 
   * if pos < 0 it inserts to the front of the list
   * if pos > size() it inserts to the end of the list
   * returns the actual position that s is added to */
  public int insert(String s, int pos){
    if(pos <= 0){
      this.insert(s);
      return 0;
    }else if(pos >= this.size()){
      Node n = getPos(head,(this.size()-1));
      n.setNext(new Node(s));
      return (this.size() - 1);
    } else {
      Node n1 = getPos(head, pos);
      Node n2 = getPos(head, (pos-1));
      Node n = new Node(s,n1);
      n2.setNext(n);
      return pos;
    }
  }
 
  /* inserts a String s to the front of the current list 
   * returns the position that the String was inserted to  */
  public int insert(String s){
    if(head == null){
      //System.out.println("entered head == null");
      runner = head;
      Node n = new Node(s);
      head = n;
      return 0;
    } else {
      //System.out.println("entered head != null");
      runner = head;
      Node next = new Node(s, runner);
      head = next;
      return 0;
    }
  }
 
 
  /* removes and returns the String in position pos 
   * or if pos is not in the range 0..size()-1, returns null and does not modify the list */
  public String remove(int pos){
    if(pos == 0){
      return this.remove();
    }else if(pos >= this.size()){
      return null;
    } else {
      Node n1 = getPos(head, pos);
      Node n2 = getPos(head, (pos-1));
      n2.setNext(n1.getNode());
      return n1.getData();
    }
  }
 
  /* removes and returns the String in the front of the list 
   * or returns null if the list is empty */
  public String remove(){
    runner = head;
    head = head.getNode();
    return runner.getData();
  }
 
 
  /* returns the String at position pos in the list 
   * or returns null if pos is not in the range 0..size()-1 
   * The list is never modified */  
  public String look(int pos){
    return getPos(head,pos).getData();
  }
 
  //to get Node at the position in the list
  private Node getPos(Node n, int i){
    if(i == 0){
      //System.out.println("In n==0");
      return head;
    }else if( i >= this.size()){
      //System.out.println("In i>size");
      return null;
    }else{
      //System.out.println("In else");
      position = position + 1;
      if(i == (position - 1)){
        position = 1;
        return n.getNode();
      }else{
        n = n.getNode();
        return getPos(n,i);
      }
    }
  }
 
  /* returns a String representation of the list.  
   * The returned String consists of all the Strings in the list, in order,
   * with a "|" (pipe) between each String. 
   * For example, if list = "cat" -> "dog" -> "eel" then the String representation
   * would be "cat|dog|eel"
   * No extra spaces are added */
   @Override
  public String toString(){
     if(head == null){
       return "";
     } else{
       return head.getData() + helper(head.getNode());
     }
  }
 
   //helper method for toString
   private String helper(Node n){
     if(n == null){
       return "";
     } else{
       return "|" + n.getData() + helper(n.getNode());
     }
   }
 
}

LinkedList Abstract:

/* Abstract class for an ordered list of Strings 
 * 
 * Strings in the list have a position, starting at 0 and
 * ending with size()-1.  (Similar to the index of an array)
 */
public abstract class LinkedListABS{
 
  /* head is the first node in the linked list */
  protected Node head;
 
 
  /* checks if list is empty or not 
   * return true if the list is empty and false otherwise*/
  public abstract boolean isEmpty();
 
  /* returns the number os Strings in the list */
  public abstract int size();
 
  /* inserts a String s into position pos of the current list 
   * if pos < 0 it inserts to the front of the list
   * if pos > size() it inserts to the end of the list
   * returns the actual position that s is added to */
  public abstract int insert(String s, int pos);
 
  /* inserts a String s to the front of the current list 
   * returns the position that the String was interred to  */
  public abstract int insert(String s);
 
 
  /* removes and returns the String in position pos 
   * or if pos is not in the range 0..size()-1, returns null and does not modify the list */
  public abstract String remove(int pos);
 
  /* removes and returns the String in the front of the list 
   * or returns null if the list is empty */
  public abstract String remove();
 
 
  /* returns the String at position pos in the list 
   * or returns null if pos is not in the range 0..size()-1 
   * The list is never modified */  
  public abstract String look(int pos);
 
 
  /* returns a String representation of the list.  
   * The returned String consists of all the Strings in the list, in order,
   * with a "|" (pipe) between each String. 
   * For example, if list = "cat" -> "dog" -> "eel" then the String representation
   * would be "cat|dog|eel"
   * No extra spaces are added */
  @Override
  public String toString(){
    return "";
  }
 
 
}

copy class:

public class CopyLinkedList{
 
  public static LinkedListABS copy(LinkedListABS list, int start, int end){
    // purpose : makes a copy of a consecutrive section of a linked list
    // input : a list of strings, two integer with start < end
    //         assume that     0 <= start < size()
    //                     start <  end   < size() + 1 
    // output : a "new" list consisting of the same strings that are found
    //          in the input list from positions start to end - 1.
    //          or, retyurn null if start/end are not valid (violating the assumed ranges above)
    // example: list = {s0,s1,s2,s3,s4,s5,s6,s7}
    //          copy(list, 2, 5) -> {s2,s3,s4}
    LinkedListABS copied = new LinkedList();
    for(; start<end; end--){
      copied.insert(list.look(end-1));
    }
    return copied;
  }
 
}

I've updated my code and realized that I would create a LinkedListABS s inside the 2 main if statements in the sort method and had a return statement under it, which I think caused the problem. I have commented them out:

if(ordered[0].size() > 2){
      System.out.println("Entered ordered[0].size() > 2");
      /*LinkedListABS s =*/ sort(ordered[0]);
      //return s;

but still I'm only getting:
order is eel|sheep|goat|mouse