Mergesort with linkedlist using recursion

• November 25th, 2013, 11:34 AM
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:
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:
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 ---

Code :

```/ 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()); } }   }```

Code :

```/* 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:
Code :

```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; }   }```
• November 25th, 2013, 11:52 AM
aussiemcgr
Re: Mergesort with linkedlist using recursion
You seem to have a lot of print statements. Are you able to also provide the printed output?
• November 25th, 2013, 12:04 PM
```if(ordered[0].size() > 2){ System.out.println("Entered ordered[0].size() > 2"); /*LinkedListABS s =*/ sort(ordered[0]); //return s;```