Merge sort a linked list

Learn how to do merge sort on a linked list in javascript.

Merge sort is a stable and fast sorting algorithm. But the problem with it uses it takes O(N) space to sort the array.

But with the linked-list we can sort the list in O(1) space that is we will not need any extra space.

How merge sort works

Conceptually this is how merge sort works

• Divide the given unsorted elements into n sub element list, each containing only one element (A single element is always sorted).
• Repeatedly merge this sub element lists in the required order until there is only one sub element list. At the end the last list will be the sorted.

Merge sort with linked list

We will use the same approach with the linked list, We will break the list in two halves and then sort and merge them.

To break the list in halves we will need to get the middle element of the list and then copy the midddle.next as upper half and start to middle as lower half.

//Sort and merge
const mergeSortWithLL = (head) => {
    if (head === null || head.next === null) {
        return head;
    }

    //Break the list from the middle
    let middle = llMiddle(head);
    let middleNext = middle.next;
    middle.next = null;

    //Sort the lower bound
    let left = mergeSortWithLL(head);

    //Sort the upper bound
    let right = mergeSortWithLL(middleNext);

    //return merged sorted list
    return sortedMerge(left, right);
};

//Merge the sorted list
const sortedMerge = (a, b) => {
    let result = null;

    if (a === null) {
        return b;
    }

    if (b === null) {
        return a;
    }

    //Recursively merge the list by calling the same function with appropriate next value
    if (a.element <= b.element) { 
       result=a; 
       result.next=sortedMerge(a.next, b); 
    } else { 
        result=b;
        result.next=sortedMerge(a, b.next); 
    } 
    return result; 
}; 

//Get the middle of the list 
const llMiddle=(head)=> {
    if (head === null) {
        return head;
    }

    let slow = head,
    fast = head;

    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
};

Input:
let ll = new linkedlist();
ll.append(40);
ll.append(10);
ll.append(35);
ll.append(70);
ll.append(22);
ll.append(3);
ll.append(5);

let sorted = mergeSortWithLL(ll.getHead());

while (sorted) {
    console.log(sorted.element);
    sorted = sorted.next;
}

Output:
3
5
10
22
35
40
70

Time complexity: O(nlogn).
Space complexity: O(1).