I try to write a merge sort with the help of singly linked list and the node definition is provided below,
public class Node {
public int item;
public Node next;
public Node(int val) {
this.item = val;
}
public Node() {
}
@Override
public String toString() {
return "Node{" +
"item=" + item +
", next=" + next +
'}';
}
}
Merge Sort works as follows:
i. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
ii. Repeatedly merge sublists to produce newly sorted sublists until there is only 1 sublist remaining. This will be the sorted list. The code is provided below.
public class MergesortWithSinglyLL {
private Node head;
public MergesortWithSinglyLL() {
head = null;
}
public boolean isEmpty() {
return (head == null);
}
public void insert(int val) {
Node newNode = new Node(val);
newNode.next = head;
head = newNode;
}
// get the end of the queue
public Node getHead() {
return head;
}
/*
Initially, this method is called recursively till there will be only one node
*/
// this mergeSort returns the head of the sorted LL
public Node mergeSort(Node head) {
/*
list is null or just one node is prevail
*/
if (head == null || head.next == null) {
return head;
}
Node a = head;
Node b = head.next;
while ((b != null) && (b.next != null)) {
head = head.next;
b = (b.next).next;
}
b = head.next;
// split the list in 2 parts now
head.next = null;
return merge(mergeSort(a), mergeSort(b));
}
// This is the merge method provided.
public Node merge(Node a, Node b) {
Node head = new Node();
Node c = head;
while ((a != null) && (b != null)) {
if (a.item <= b.item) {
c.next = a;
// c = a;
c = c.next;
a = a.next;
} else {
c.next = b;
// c = b;
c = c.next;
b = b.next;
}
}
// define the last element of the ll
c.next = (a == null) ? b : a;
return head.next;
}
public void display() {
Node current = head;
String result = "";
while (current != null) {
result += " " + current.item + " ";
current = current.next;
}
System.out.println(result);
}
}
I make the initiation call like this,
int[] arr = {12, 3, 4, 56, -7, -6, -5, 1};
MergesortWithSinglyLL merges = new MergesortWithSinglyLL();
for (int i = 0; i < arr.length; i++) {
merges.insert(arr[i]);
}
merges.mergeSort(merges.getHead());
merges.display();
The result is 3 4 12 56
and it seems that all the negative values are disappearing. What is the issue here?
Your implementation is fine, the error is in what you call the initiation call.
mergeSort returns the sorted list but you don't assign it so you end up with a subset of the solution.
If you replace this line
merges.mergeSort(merges.getHead());
with this line
merges.head = merges.mergeSort(merges.getHead());
(of course you'll have to make MergesortWithSinglyLL.head public)
You'll see that you get the correct sorted list as a result.