Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

1. ## 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{

// 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;
}

// 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);
System.out.println("s1 is: " + s1.toString());
System.out.println("s2 is: " + s2.toString());
System.out.println("ordered[0] is " + ordered[0] + " ordered[1] is " + ordered[1]);
return ordered;
}else{
System.out.println("Entered size <=1");
System.out.println("ordered is " + ordered[0]);
return ordered;
}

}

// 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");

System.out.println("copy created: " + copied.toString());
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");
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");
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());
}

n = m;
//}

return n;
}

}```

test code:
```public class MergeTest{

public static void main(String[] args){

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());
System.out.println("order is " + order.toString());
System.out.println("list: " + list.toString());

}
}```

--- Update ---

```/

private int position = 1; //variable to hold the position of the node
private Node runner;

// zero parameter constructor
}

/* checks if list is empty or not
* return true if the list is empty and false otherwise*/
public boolean isEmpty(){
return true;
}else{
return false;
}
}

/* returns the number of Strings in the list */
public int size(){
int s = 0;
if(runner == null){
return 0;
} else if(runner != null){
} 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()){
n.setNext(new Node(s));
return (this.size() - 1);
} else {
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){
Node n = new Node(s);
return 0;
} else {
Node next = new Node(s, runner);
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 {
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(){
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){
}

//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");
}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(){
return "";
} else{
}
}

//helper method for toString
private String helper(Node n){
if(n == null){
return "";
} else{
return "|" + n.getData() + helper(n.getNode());
}
}

}```

```/* 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)
*/

/* 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{

// 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}
for(; start<end; end--){
copied.insert(list.look(end-1));
}
return copied;
}

}```

2. ## Re: Mergesort with linkedlist using recursion

You seem to have a lot of print statements. Are you able to also provide the printed output?

3. ## Re: Mergesort with linkedlist using recursion

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");