merge sort of linked list

gistfile1.java

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;
	}
}