# C++ O(1) space merge sort (non-recursive, constant stack space usage)

• ``````class Solution {
public:
// Cut the first n items of list p to form a new list
// Return the pointer to the following item (the= (n+1)th item) in p
ListNode* cutN(ListNode *p, int n) {
ListNode *last = nullptr;
while(n && p) {
last = p;
p = p->next;
n --;
}
if (last)
last->next = nullptr;
return p;
}

// Merge list a and list b
// Return pointers to the first and the last item in the merged list
pair<ListNode*, ListNode*> merge(ListNode *a, ListNode *b) {
ListNode *first = nullptr;
ListNode *last = nullptr;

while (a || b) {
ListNode *next = nullptr;
if (a && (!b || a->val < b->val)) {
next = a;
a = a->next;
} else {
next = b;
b = b->next;
}
if (!first) first = next;
if (last) last->next = next;
last = next;
}
return {first, last};
}

// Count the total number of nodes
int n=0;
while (p) {
n ++;
p = p->next;
}

// Before each iteration, every s items in the list is already sorted,
// the list contains n/s sorted runs.
// In each iteration, every 2 adjacent sorted runs are merged into a 2s-item sorted run
// This loop is executed log(2, n) times
for (int s=1; s<n; s<<=1) {
ListNode *a, *b;

// This loop is executed n/s times
while (next) {
// cutN() takes O(s) time
a = next;
b = cutN(next, s);
next = cutN(b, s);

// Merge() takes O(s) time
auto p = merge(a, b);
(*last) = p.first;
p.second->next = next;
last = &(p.second->next);
}
}