When I insert numbers in my linked list it only sorts everything when the first number added to it is the smallest. This is the unexpected behavior that I am getting:
I insert the numbers in this order - 200, 25, 473, 23, 390
If I sort the list like that above and display it, I get this - 200, 390, 473
If I change 200 to 900 then sort the list, it only displays 900
It only works when I change 200 to the smallest number in the list like 1 (or anything less than 23), then it gives me the right output 1, 23, 25, 390, 473
For the linked list I insert the elements at the back of the the list, this is the code:
public void insertAtBack(IntegerElement elem) {
if (isFull()) {
System.out.println("Unable to insert node into full list");
} else {
Node temp = new Node(elem);
if (isEmpty()) {
head = temp;
} else {
Node current = head;
while (current.getLink() != null) {
current = current.getLink();
}
current.setLink(temp);
}
}
}
And this is the code I use to merge sort:
public Node getMiddle(Node node) {
if (node == null)
return node;
Node fastptr = node.getLink();
Node slowptr = node;
// Move fastptr by two and slow ptr by one
// Finally slowptr will point to middle node
while (fastptr != null) {
fastptr = fastptr.getLink();
if(fastptr != null) {
slowptr = slowptr.getLink();
fastptr = fastptr.getLink();
}
}
return slowptr;
}
public Node merge(Node left, Node right) {
Node tempHead = new Node(), curr;
curr = tempHead;
while(left != null && right != null) {
if(left.getData().getValue() <= right.getData().getValue()) {
curr.setLink(left);
left = left.getLink();
}else {
curr.setLink(right);
right = right.getLink();
}
curr = curr.getLink();
}
curr.setLink((left == null) ? right : left);
return tempHead.getLink();
}
/**
* This method utilizes merge sort algorithm
*
* @param node - Pass in head first
*
*/
public Node sort(Node node) {
// Base case : if head is null
if (node == null || node.getLink() == null)
return node;
// get the middle of the list
Node middle = getMiddle(node);
Node nextofmiddle = middle.getLink();
// set the next of middle node to null
middle.setLink(null);
// Merge the left and right lists
return merge(sort(node), sort(nextofmiddle));
}
Any help is appreciated
Your sort routine looks great. The bug appears to be the way you are returning from your sort routine. If you call your sort as if it were an in-place sort, i.e.
sort(head);
System.out.println(head);
the old head is not updated to the new head returned by sort(). Notice how the nodes that are being displayed in your test cases always begin with whatever the old head was. This appears to work if the old head in the unsorted list happens to be the new head in the sorted list, as in your last example. If, on the other hand, the old head node is moved during the sort, you'll only see the rest of the list from wherever the old head moved to onward. Nodes from the front of the list up to the old head will be garbage collected when they go out of scope.
The fix is to set the head of your list in the caller to the returned head from sort(), which is the new head of the list:
head = sort(head);
System.out.println(head);
Here's your code re-written which reproduces your errors to illustrate the problem:
class Main {
public static void main(String[] args) {
Node head = new Node(200, new Node(25, new Node(473, new Node(23, new Node(390, null)))));
System.out.println("Example 1 (correct):");
System.out.println(head);
head = sort(head);
System.out.println(head);
head = new Node(200, new Node(25, new Node(473, new Node(23, new Node(390, null)))));
System.out.println("\nExample 1 (incorrect):");
System.out.println(head);
sort(head);
System.out.println(head);
head = new Node(900, new Node(25, new Node(473, new Node(23, new Node(390, null)))));
System.out.println("\n\nExample 2 (correct):");
System.out.println(head);
head = sort(head);
System.out.println(head);
head = new Node(900, new Node(25, new Node(473, new Node(23, new Node(390, null)))));
System.out.println("\nExample 2 (incorrect):");
System.out.println(head);
sort(head);
System.out.println(head);
head = new Node(1, new Node(25, new Node(473, new Node(23, new Node(390, null)))));
System.out.println("\n\nExample 3 (accidentally works, because the old head is still the new head):");
System.out.println(head);
sort(head);
System.out.println(head);
}
static Node getMiddle(Node node) {
Node fastptr = node.link;
Node slowptr = node;
while (fastptr != null) {
fastptr = fastptr.link;
if (fastptr != null) {
slowptr = slowptr.link;
fastptr = fastptr.link;
}
}
return slowptr;
}
static Node merge(Node left, Node right) {
Node temp = new Node(-1, null);
Node curr = temp;
while (left != null && right != null) {
if (left.data < right.data) {
curr.link = left;
left = left.link;
}
else {
curr.link = right;
right = right.link;
}
curr = curr.link;
}
curr.link = left == null ? right : left;
return temp.link;
}
static Node sort(Node node) {
if (node == null || node.link == null) {
return node;
}
Node middle = getMiddle(node);
Node next = middle.link;
middle.link = null;
return merge(sort(node), sort(next));
}
}
class Node {
public int data;
public Node link;
public Node(int data, Node link) {
this.data = data;
this.link = link;
}
public String toString() {
return this.data + (this.link != null ? "->" + this.link : "");
}
}
Output:
Example 1 (correct):
200->25->473->23->390
23->25->200->390->473
Example 1 (incorrect):
200->25->473->23->390
200->390->473
Example 2 (correct):
900->25->473->23->390
23->25->390->473->900
Example 2 (incorrect):
900->25->473->23->390
900
Example 3 (accidentally works, because the old head is still the new head):
1->25->473->23->390
1->23->25->390->473