Why doesn't this merge-sort function cause an infinite loop?

Question

I'm working on a project that requires me to implement merge-sort on a linked list and I am using the code from this post Here to help me. Can someone explain to why on line 6, when I call return merge(merge_sort(head),merge_sort(sHalf)); the method merge_sort(head) inside of it, which contains the same head pointer doesn't cause an infinite loop? It seems to me that it is starting all over again with the same head pointer.

public Node merge_sort(Node head) {
    if(head == null || head.next == null) { return head; }
    Node middle = getMiddle(head);      //get the middle of the list
    Node sHalf = middle.next; middle.next = null;   //split the list into two               halfs

    return merge(merge_sort(head),merge_sort(sHalf));  //recurse on that
}

//Merge subroutine to merge two sorted lists
public Node merge(Node a, Node b) {
    Node dummyHead, curr; dummyHead = new Node(); curr = dummyHead;
    while(a !=null && b!= null) {
        if(a.info <= b.info) { curr.next = a; a = a.next; }
        else { curr.next = b; b = b.next; }
        curr = curr.next;
    }
    curr.next = (a == null) ? b : a;
    return dummyHead.next;
}

//Finding the middle element of the list for splitting
public Node getMiddle(Node head) {
    if(head == null) { return head; }
    Node slow, fast; slow = fast = head;
    while(fast.next != null && fast.next.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    return slow;
}

Alternate bottom up method for sorting link lists, simple and faster than scanning lists to split them. Wiki has an example similar to what is used in std::list::sort. It uses the same merge function as what you have in your code. [bottom merge sort for lists](http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists) — rcgldr, Dec 05 '15 at 06:04

score 1 · Accepted Answer · answered Dec 05 '15 at 04:44

It's because of the previous line:

Node sHalf = middle.next; middle.next = null;

Specifically, the middle.next = null; part.

Understand that even though the head pointer is the same, we are splitting the list into half, using middle.next = null. So, in the next recursive call, it's only half the linked list which was sent originally.

And at one point, it will reach head.next == null condition.

Why doesn't this merge-sort function cause an infinite loop?

1 Answers1