Sort a Single Linked List Using merge sort

Merge Sort:
Merge Sort works on divide and conquer principle. First we have to split the unsorted list to sublist till each sub-lists has only one element, and then merge the sub-lists.

Why QuickSort is not worthy for LinkedList?
As we know Quick sort, average time complexity is O(n2), if we use random quick sort then we can say that the average time complexity is O(nlogn), But in Single link it is too difficult to find a random node. That's the reason Quick sort is not good choice for linkedlist.


Code Implementation:

public static LinkList<Integer> mergeSort(LinkList<Integer> list) {
        if (list != null && list.getNext() != null) {
            LinkList<Integer>[] lists = split(list);
            lists[0] = mergeSort(lists[0]);
            lists[1] = mergeSort(lists[1]);
            return merge(lists[0], lists[1]);
        }
        return list;
    }

    private static LinkList<Integer> merge(LinkList<Integer> linkList,
            LinkList<Integer> linkList2) {
        LinkList<Integer> retval = null;
        if (linkList == null)
            return linkList2;
        if (linkList2 == null)
            return linkList;
        if (linkList.getData() < linkList2.getData()) {
            retval = linkList;
            linkList = linkList.getNext();
            retval.setNext(null);
        } else {
            retval = linkList2;
            linkList2 = linkList2.getNext();
            retval.setNext(null);
        }
        LinkList<Integer> header = retval;
        while (linkList != null && linkList2 != null) {
            if (linkList.getData() < linkList2.getData()) {
                retval.setNext(linkList);
                linkList = linkList.getNext();
                retval = retval.getNext();
                retval.setNext(null);
            } else {
                retval.setNext(linkList2);
                linkList2 = linkList2.getNext();
                retval = retval.getNext();
                retval.setNext(null);
            }
        }
        if (linkList2 != null) {
            retval.setNext(linkList2);
        }
        if (linkList != null) {
            retval.setNext(linkList);
        }
        return header;
    }

    @SuppressWarnings("unchecked")
    private static LinkList<Integer>[] split(LinkList<Integer> list) {
        if (list == null || list.getNext() == null) {
            return (LinkList<Integer>[])(new LinkList<?>[] { list, null});
        }
        LinkList<Integer> slow = list;
        LinkList<Integer> fast = list.getNext();
        while (fast != null) {
            fast = fast.getNext();
            if (fast != null) {
                fast = fast.getNext();
                slow = slow.getNext();
            }

        }
        LinkList<Integer> second = slow.getNext();
        slow.setNext(null);
        return new LinkList[] { list, second };
    } 

class LinkList<T> {
    public LinkList() {
    }

    public LinkList(T data) {
        this.data = data;
    }
    private T data;
    private LinkList<T> next;

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public LinkList<T> getNext() {
        return next;
    }
    public void setNext(LinkList<T> next) {
        this.next = next;
    }
   
}