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

• 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) {

//bottom up merge sort imp
int len = 0;
// get length of list.
while(node != null){
node = node.next;
len++;
}

ListNode dummyNode = new ListNode(0);
// 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;
}``````

• does this satisfy the constant space criteria ?

• 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. :]

• 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.

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