Merge sort linked list

Merge sort, compared to quick sort has the best and worst time complexity of O(NLgN) and requires O(N) space.

However for linked list, merge sort doesn't require additional space.

	public class SortQ {
	public static class Node {
	int d;
	Node next;
	}
	public static Node merge_sort2(Node head){
	assert(head!=null);
	if(head.next == null)
	return head;
	Node fast = head, slow = head;
	while(fast!=null && fast.next !=null){
	fast = fast.next.next;
	slow = slow.next;
	}
	Node right;
	if(slow.next!=null){
	right = slow.next;
	//cut half
	slow.next = null;
	}else{
	right = head.next;
	head.next = null;
	}
	Node sortLeft = merge_sort2(head).next;
	Node sortRight = merge_sort2(right).next;
	//create fake head
	Node ret = new Node();
	Node p = ret;
	while(sortLeft!=null && sortRight!=null){
	if(sortLeft.d > sortRight.d){
	p.next = sortLeft;
	sortLeft = sortLeft.next;
	}else{
	p.next = sortRight;
	sortRight = sortRight.next;
	}
	p = p.next;
	}
	if(sortLeft!=null)
	p.next = sortLeft;
	if(sortRight!=null)
	p.next = sortRight;
	return ret;
	}
	public static Node merge_sort(Node head){
	int size = 0;
	Node current = head;
	while(current!=null)
	size++;
	return merge_sort(head, 0, size-1);
	}
	public static Node merge_sort(Node head, int start, int end){
	if(start==end)
	return head;
	int mid = (start+end)>>>1;
	Node left = merge_sort(head, start, mid);
	Node current = head;
	int counter = 0;
	while(counter<=mid-start)
	current = current.next;
	Node right = merge_sort(current, mid+1, end);
	int leftC = 0, rightC =0;
	Node result;
	if(left.d > right.d){
	result = left;
	left = left.next;
	leftC++;
	}
	else {
	result = right;
	right = right.next;
	rightC++;
	}
	Node p = result;
	while(leftC < mid - start + 1 && rightC < end - mid ){
	if(left.d > right.d){
	p.next = left;
	left = left.next;
	leftC++;
	}else{
	rightC++;
	p.next = right;
	right = right.next;
	}
	p = p.next;
	}
	if(leftC++ < mid - start + 1)
	p.next = left;
	if(rightC++ < end - mid)
	p.next = right;
	return head;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub