MergeSortList.java

package linkedlist;



public class MergeSortList {

    /*
     * Given head pointer of a linked sort, sort linked list (in ascending order) using merge sort
     * and return new head pointer of sorted linked list.
     * Input: List1: 29 -> 23 -> 82 -> 11
     * Output:  11 -> 23 -> 29 -> 82
     *
     * */

    /*
     * Runtime Complexity:
     * Linearithmic i.e. O(n * log n)
     *
     * Memory complexity:
     * Logarithmic, O(log n)
     *
     *
     * The concept of merge sort is very straightforward.
     * In the dividing step, split the input linked list into two halves and keep doing it until there is a linked list of size 1 or 0.
     * Linked lists of size 1 and 0 are always sorted. In the combining step, merge sorted lists and keep doing this until
     * there is a completely sorted list. Recurrence relation for this merge sort algorithm will be:
     *
     * T(n) = 2T(n/2) + nT(n)=2T(n/2)+n
     * At each step, divide the problem into two sub-problems and size of each sub-problem is n/2 and total cost of combining step
     * (merging sorted lists) is n.
     * If we solve this recurrence relation, the result will be O(n * log n) which is the time complexity of merge sort
     * */


    // this method splits linked list in two halves by iterating over whole list
    // It returns head pointers of first and 2nd halves of linked lists in first_second
    // Head of 1st half is just the head node of linked list
    private static void splitInHalf(LinkedList.Node head,
                                    Pair<LinkedList.Node, LinkedList.Node> firstSecondPair) {

        if (head == null) {
            return;
        }

        // Only one element in the list.
        if (head.next == null) {

            firstSecondPair.first = head;
            firstSecondPair.second = null;
        } else {

            // Let's use the classic technique of moving two pointers:
            // 'fast' and 'slow'. 'fast' will move two steps in each
            // iteration where 'slow' will be pointing to middle element
            // at the end of loop.

            LinkedList.Node slow, fast;
            slow = head;
            fast = head.next;

            while (fast != null) {

                fast = fast.next;

                if (fast != null) {

                    fast = fast.next;
                    slow = slow.next;
                }
            }

            firstSecondPair.first = head;
            firstSecondPair.second = slow.next;

            // Terminate first linked list.
            slow.next = null;
        }
    }

    private static LinkedList.Node mergeSortedLists(LinkedList.Node first,
                                                    LinkedList.Node second) {

        if (first == null) {
            return second;
        } else if (second == null) {
            return first;
        }

        LinkedList.Node new_head;
        if (first.data <= second.data) {
            new_head = first;
            first = first.next;
        } else {
            new_head = second;
            second = second.next;
        }

        LinkedList.Node new_current = new_head;
        while (first != null && second != null) {
            LinkedList.Node temp = null;
            if (first.data <= second.data) {
                temp = first;
                first = first.next;
            } else {
                temp = second;
                second = second.next;
            }

            new_current.next = temp;
            new_current = temp;
        }

        if (first != null) {
            new_current.next = first;
        } else if (second != null) {
            new_current.next = second;
        }

        return new_head;
    }

    public static LinkedList.Node mergeSort(LinkedList.Node head) {

        // No need to sort a single element.
        if (head == null || head.next == null) {
            return head;
        }

        Pair<LinkedList.Node, LinkedList.Node> first_second = new Pair<LinkedList.Node, LinkedList.Node>(null, null);

        // Let's split the list in half, sort the sublists
        // and then merge the sorted lists.
        splitInHalf(head, first_second);

        first_second.first = mergeSort(first_second.first);
        first_second.second = mergeSort(first_second.second);

        return mergeSortedLists(first_second.first, first_second.second);
    }


    public static class Pair<K, V> {

        private K first;
        private V second;

        public static <K, V> Pair<K, V> createPair(K element0, V element1) {
            return new Pair<K, V>(element0, element1);
        }

        public Pair(K first, V second) {
            this.first = first;
            this.second = second;
        }

        public K getFirst() {
            return first;
        }

        public V getSecond() {
            return second;
        }

    }

    public static class LinkedList {

        private Node head;

        public Node head() {
            return head;
        }

        public void printNode(Node node) {
            while (node != null) {
                System.out.print(node.data + " ");
                node = node.next;
            }
        }

        /* Inserts a new Node at end of the list. */
        public void push(int new_data) {
            Node newNode = new Node(new_data);
            if (head == null) {
                head = new Node(new_data);
                return;
            }

            newNode.next = null;
            Node last = head;
            while (last.next != null) {
                last = last.next;
            }
            last.next = newNode;
        }

        public static class Node {
            private Node next;
            private Integer data;

            public Node(Integer data) {
                this.data = data;
            }

            public Node next() {
                return next;
            }

            public void setNext(Node next) {
                this.next = next;
            }

            public Integer data() {
                return data;
            }

            public void setData(Integer data) {
                this.data = data;
            }
        }
    }


    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.push(8);
        linkedList.push(15);
        linkedList.push(1);
        linkedList.push(19);
        linkedList.push(2);
        linkedList.push(1);


        System.out.println("Original: ");
        linkedList.printNode(linkedList.head);
        System.out.println();
        System.out.println("Sorted: ");
        LinkedList.Node mergedList = mergeSort(linkedList.head);
        linkedList.printNode(mergedList);
    }
}