Mergesort with singly linked list

Question

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?

can you please make your input array {-7, -6, -5, 1, 12, 3, 4, 56} and tell us what the result is — hovanessyan, Apr 02 '18 at 10:42
@hovanessyan with that input, I only get `56` as result. I wonder where its wrong — Arefe, Apr 02 '18 at 10:49
So it seems that the algorithm only considers te last number itself and numbers larger than it. — Arefe, Apr 02 '18 at 10:54
Maybe consider reworking your implementation. Here is an example of a working implementation: https://stackoverflow.com/a/8238253/1007273 — hovanessyan, Apr 02 '18 at 10:55
Looks similar but I still can't find what the real issue. Maybe something trivial is missing in my eyes. — Arefe, Apr 02 '18 at 11:16
If you know the logic of the algorithm, re-writing it from scratch helps. Just re-write it again and follow closely the steps of the algorithm. — hovanessyan, Apr 02 '18 at 11:17
@hovanessyan that might be better as debugging the recursive algo is little hard. — Arefe, Apr 02 '18 at 11:19

score 4 · Accepted Answer · answered Apr 02 '18 at 14:41

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.

Thanks a lot. This is very helpful. – Arefe Apr 02 '18 at 14:44 — Arefe, Apr 02 '18 at 14:44

Mergesort with singly linked list

1 Answers1