LinkedListMergeSort.js

const util = require('util');

class Node {
	constructor(data, next=null) {
		this.data = data;
		this.next = next;
	}
}
class LL {
	constructor() {
		this.root = null
	}
	insert(data) {
		if(!this.root) {
			this.root = new Node(data);
		} else {
			let node = this.root;
			while(node.next) {
				node = node.next;
			}
			node.next = new Node(data);
		}
	}

	sort() {
		this.root = this.mergeSort(this.root);
	}


	mergeSort(node) {
		if(!node) {
			return;
		}
		if(!node.next) {
			return node;
		}

		let slow = node;
		let fast = node.next;

		while(fast && fast.next) {
			fast = fast.next.next;
			slow = slow.next;
		}
		let backHalf = slow.next;
		slow.next = null;
		let frontHalf = node;

		console.log('Front Half: ' + util.inspect(frontHalf, false, null, true));
		console.log('Back Half: ' + util.inspect(backHalf, false, null, true))

		return this.merge(this.mergeSort(frontHalf), this.mergeSort(backHalf));
	}

	merge(left, right) {
		let list = new LL()
		while(left || right) {
			if(!left && right) {
				list.insert(right.data);
				right = right.next;
			} else if(!right && left) {
				list.insert(left.data);
				left = left.next;
			} else if(left.data < right.data) {
				list.insert(left.data);
				left = left.next
			} else {
				list.insert(right.data);
				right = right.next
			}
		}
		console.log('Sorted List: ' + util.inspect(list, false, null, true));
		return list.root;
	}

	printList() {
		let node = this.root;
		while(node) {
			console.log(node.data);
			node = node.next;
		}
	}
}

let list = new LL();
list.insert(4);
list.insert(1);
list.insert(3);
list.insert(99);
list.insert(2);
list.insert(12);
list.insert(8)

list.printList();
list.sort();
list.printList();