My Java solution [Bottom-up/Iterative merge sort WITH detailed comments!]


  • 2
    W

    Hello! Please don't be afraid of the length of the provided solution. This is due to the extensive comments that I have laid out for reference and for those who are interested in a walk-through the code. The general idea for a bottom-up merge sort is essentially the same as the top-down approach. However, in this case, we have to simulate the recursion process in the form of loops (and in-place). We still have the partition (i.e. starting from a 1-element sublist and etc.) and merging process.
    Feel free to let me know should you have any queries regarding the algorithm/code OR if my solution can be improved upon! :)

    public ListNode sortList(ListNode head) {
            if(null == head)
                return head;
            if(head.next == null)
                return head;    
            
            //bottom up merge sort imp
            int len = 0;
            // get length of list.
            ListNode node = head;
            while(node != null){
                node = node.next;
                len++;
            }
            
            ListNode dummyNode = new ListNode(0);
    		dummyNode.next = head;
    		// width = width * 2 ==> because we want to mergeSort nodes in pairs/at
    		// power of 2s -- starting from 1. e.g. 1 -> 2 -> 4 -> 8 -> ...
    		// so...the initial iteration will be mergeSorting the nodes 1-by-1 then
    		// 2-by-2 then etc.
    		for (int width = 1; width < len; width *= 2) {
    			// re-initialize leftList (back to the head!) whenever the width is
    			// updated - we want to
    			// iterate through the list again from the beginning but
    			// this time is a different pair width/size.
    			ListNode leftList = dummyNode.next;
    			// this var is meant to keep track of sub-lists that come before the
    			// sub-list/pair that we are about to merge/sort (in the
    			// inner-loop).
    			// after merging, they are linked back together again.
    			// e.g. 1->2->4->3 ==> 1->2 merge(4, 3) ==> 1->2->3->4
    			ListNode beforeCurrMergedList = null;
    			// This (inner) loop will be doing the traversal of the list with
    			// respect to the size of the width!
    			// j = width * 2 ==> 0 + 1*2 == 2 -> 2 + 1*2 == 4 ==> we are sliding
    			// through the list within the specified window/width!
    			// so, if we have a list of 4 nodes and if the current width is 1,
    			// this loop will only be iterating twice.
    			// within this loop, each width/pair will be handled accordingly.
    			// e.g. if the current width is 1 and this is the first iteration of
    			// the inner loop, the first two nodes will be sorted. {left = 1st
    			// node and right = 2nd node}
    			// so, when we are out of an iteration, we can assume that the
    			// current pair has been sorted and we are now moving to the next
    			// set of pairs.
    			for (int j = 0; j < len; j = j + width * 2) {
    				// We have the starting left node/list -- we need to get the
    				// right node/list.
    				// This is done w.r.t the current width.
    				ListNode tempNode = leftList;
    				// we stop right BEFORE the beginning of the right node/list.
    				for (int i = 1; tempNode != null && i < width; i++) {
    					tempNode = tempNode.next;
    				}
    				// precaution purposes. :]
    				if (null == tempNode)
    					break;
    				// initialize the right list's starting point.
    				ListNode right = tempNode.next;
    				// this will happen if the current node is in an odd pair i.e.
    				// has no right node/list to pair with.
    				if (null == right)
    					break;
    				// we want segregate/partition the left and right sub-lists to
    				// make merging slightly easier (and less messy IMO).
    				// so, the last node of the left list will point to NOTHING
    				// instead of the original starting point of the right list.
    				tempNode.next = null;
    				// this portion of the code is dedicated to segregating the
    				// right list from the REST of the list so that we can assume
    				// the left and right sub-lists to be self-contained.
    				// don't worry, we'll attach them back later!
    				ListNode remainders = null;
    				if (right.next != null) {
    					// contains the (starting point of) sub-lists that come
    					// after the right
    					// sub-list.
    					remainders = right.next;
    					ListNode beforeRemainder = right;
    					for (int i = 1; remainders != null && i < width; i++) {
    						beforeRemainder = beforeRemainder.next;
    						remainders = remainders.next;
    					}
    					// last node of the right sub-list points to nothing.
    					beforeRemainder.next = null;
    				}
    				// merge the left and right sub-lists together!
    				// this operation is exactly the same as the one that is done in
    				// the top-down/recursive merge sort algorithm.
    				ListNode mergedList = merge(leftList, right);
    				// We want to iterate to the last node of the now merged/sorted
    				// sub-list so that we can re-attach the previously detached
    				// (right-side/back) sub-list back to the merged sub-list.
    				// remember? :]
    				tempNode = mergedList;
    				while (tempNode.next != null) {
    					tempNode = tempNode.next;
    				}
    				tempNode.next = remainders;
    
    				// we also want to re-attach the previously detached
    				// (left-side/front) sub-list back to the FRONT of the merged
    				// sub-list. remember?! :]
    				if (beforeCurrMergedList != null)
    					beforeCurrMergedList.next = mergedList;
    				// now, the pointer for the to-be detached left-side/front
    				// sub-list is updated to the end of the now merged/sorted
    				// sub-list. Why at the last node? This is so that we can call
    				// .next easily later on! (when doing the re-attachment)
    				beforeCurrMergedList = tempNode;
    				// We then update the left sub-list to be the starting point of
    				// the next pair of nodes (again, this is all according to the
    				// width) -- and the cycle continues...
    				leftList = tempNode.next;
    				if (j == 0)
    					// We want the head of the entire list to be updated at all
    					// times.
    					// things might shift around during the mergeSort operation.
    					// of course, it is updated only during the FIRST iteration
    					// of the inner loop.
    					// updating during subsequent iterations is unnecessary
    					// since the leftList/mergedList has shifted towards the
    					// back of the list as the loop goes on.
    					dummyNode.next = mergedList;
    			}
    		}
            
            return dummyNode.next;
        }
    
    private ListNode merge(ListNode left, ListNode right){
            ListNode dummy = new ListNode(0);
            ListNode dummyPtr = dummy;
            ListNode leftPtr = left;
            ListNode rightPtr = right;
            while(leftPtr != null && rightPtr != null){
                if(leftPtr.val <= rightPtr.val){
                    dummyPtr.next = leftPtr;
                    leftPtr = leftPtr.next;
                }else{
                    dummyPtr.next = rightPtr;
                    rightPtr = rightPtr.next;
                }
                    
                dummyPtr = dummyPtr.next;
            }
            
            //link the remainders if they exist
            if(leftPtr != null)
                dummyPtr.next = leftPtr;
            else if(rightPtr != null)
                dummyPtr.next = rightPtr;
            
            return dummy.next;
        }

  • 0
    R

    does this satisfy the constant space criteria ?


  • 0
    W

    Hi! Yeap, it does indeed. Initially, the implementation was top-down but recursion uses up at least log(n) of stack space. So, I went with bottom-up in the end. :]


  • 0
    I

    not very useful unfortunately, i'd recommend writing a proper article with a detailed explanation. The code works and all but it's a pain to actually figure out what's going on.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.