# True O(1) space bottom up Merge Sort

• As I said in another post, anything that uses recursion is O(log N) space complexity.
Here is my bottom up iterative merge sort solution. Took me a lot of time to compress it to under 50 lines.
It will be much harder to implement/debug if we don't count the length of the list first, so bear with me.
Also it is very hard to debug if we don't take up the next two sub-list out of the original list and NULL their ends.

``````class Solution {
public:
ListNode dummy(0), *prev = &dummy;
int sz = 1;//cur merge size
int n = 0;//list.size()
for(ListNode* p = head; p; ++n, p = p->next); //Get Length
for(int sz = 1; sz/2 < n; sz += sz) {
prev = &dummy;
while(1) {
ListNode* l1 = prev->next, *l2, *rest;
for(int steps = 0; steps < sz-1 && l1->next; ++steps, l1 =l1->next);    //ready to set up list 1
if(!l1->next) break;   //if we encounter NULL then nothing to merge
l2 = l1->next;    // ready to set up list 2
for(int steps = 0; steps < sz-1 && l2->next; ++steps, l2 = l2->next);
rest = l2->next;   // mark the beginning of the rest of the list
l2->next = NULL;   // NULL the end of list 2
l2 = l1->next;        // set the head of list 2
l1->next = NULL;  //NULL the end of list 1
l1 = prev->next;   //set the head of list 1
ListNode* newTail;    // one of the output of the merge function, i.e., the tail of the merged list
l1 = merge(l1, l2, newTail);
prev->next = l1;
newTail->next = rest;
prev = newTail;
if(!rest) break;
}
}
return dummy.next;
}

ListNode* merge(ListNode*l1, ListNode* l2, ListNode* &newTail) { //sz: the size of each sorted list
ListNode dummy(0);
newTail = &dummy;
while(l1 && l2) {
if(l1->val < l2->val) {
newTail->next = l1;
l1 = l1->next;
} else {
newTail->next = l2;
l2 = l2->next;
}
newTail = newTail->next;
}
l1 ? newTail->next = l1 : newTail->next = l2;
for( ; newTail->next; newTail = newTail->next);
return dummy.next;
}
};``````

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