Tuesday 1 December 2015

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

1 comment:

  1. Sands Casino: A Casino in the Upper Peninsula of Nevada
    A casino in the Upper Peninsula 메리트카지노 of Nevada. Sands Casino is a top-rated Las Vegas casino and is located 샌즈카지노 on the 메리트 카지노 주소 famous Strip. It is owned by

    ReplyDelete