CareerCup

// merge sort: returns a pointer to the head of a sorted list
list *merge_sort(list *head) {
    if(head == 0)
        return 0;
    list *p = head, *pp = p, *prev = 0
    if(p->next == 0)
        return head; // already sorted
    // find a split in the middle using two ptrs
    while(pp != 0 && pp->next != 0) {
        prev = p, p = p->next;
        pp = pp->next->next;
    }
    prev->next = 0; // cut the list in the middle
    list *h1 = merge_sort(p),
         *h2 = merge_sort(head);   // sort the two parts

    head = h1, prev = 0;
    // merge the list 'h2' into 'h1' inplace
    while(h2 != 0) {
        if(h1 != 0 && h2->val >= h1->val) {
            prev = h1;      // just iterater through 'h1' list
            h1 = h1->next;
        } else { // insert 'h2' before 'h1'
            list *t = h2->next; // save the 'next' pointer
            if(prev == 0) { // insert a new head
                h2->next = head;
                head = h2;
            } else {
                prev->next = h2;
                h2->next = h1;
            }
            prev = h2; h2 = t;
        }
    }
    return head;
}

public void mergeSort() {
		this.sortedHead = split(getHead());
	}



private LinkListNode<E> split(LinkListNode<E> head) {
		if (head.getNext() == null || head == null)
			return head;

		LinkListNode<E> firstHalf = getMiddleElement(head);
		LinkListNode<E> secondHalf = firstHalf.getNext();
		firstHalf.setNext(null);
		head = merge(split(head), split(secondHalf));
		return head;
	}

	private LinkListNode<E> merge(LinkListNode<E> splitHead1,
			LinkListNode<E> splitHead2) {

		LinkListNode<E> dummyHead = new LinkListNode<E>();
		LinkListNode<E> lastPos = dummyHead;

		while (splitHead1 != null && splitHead2 != null) {
			if ((Integer) splitHead1.getData() <= (Integer) splitHead2
					.getData()) {
				lastPos.setNext(splitHead1);
				splitHead1.setPrev(lastPos);
				splitHead1 = splitHead1.getNext();
				lastPos = lastPos.getNext();
			} else {
				lastPos.setNext(splitHead2);
				splitHead2.setPrev(lastPos);
				splitHead2 = splitHead2.getNext();
				lastPos = lastPos.getNext();
				
			}
		}

//If any remaining elements in any of the two link lists ... 

		while (splitHead1 != null) {
			lastPos.setNext(splitHead1);
			splitHead1.setPrev(lastPos);
			splitHead1 = splitHead1.getNext();
			lastPos = lastPos.getNext();
			
		}

		while (splitHead2 != null) {
			lastPos.setNext(splitHead2);
			splitHead2.setPrev(lastPos);
			splitHead2 = splitHead2.getNext();
			lastPos = lastPos.getNext();
			
		}
		return dummyHead.getNext();
	}

	private LinkListNode<E> getMiddleElement(LinkListNode<E> head) {
		if (head == null)
			return null;
		if (head.getNext() == null)
			return head;

		int count = 0;
		LinkListNode<E> fastP = head, slowP = head;
		while (fastP.getNext() != null) {
			fastP = fastP.getNext();
			count++;
			if (count % 2 == 0)
				slowP = slowP.getNext();
		}
		return slowP;
	}