# Button up merge sort with constant space

• The idea is bottom up merge sort. Recursive version is not really constant space if considering stack.
It's a little bit tricky to code this up. My python code for your reference.

``````class Solution:
# @param {ListNode} head
# @return {ListNode}
def sortList(self, head):
dummy = ListNode(0)
dummy.next = head
sz = 1               # size of the list that will be merged
length = self.lenList(head)
while sz < length:   # if the whole list is not long enough for the other sub list, merge is over
cur = dummy.next # start from first node
last = dummy     # tail node of previous merged lists
while cur:
prev = last
h1 = cur     # first sub list
for x in range(sz):
if not cur:
break
cur = cur.next
prev = prev.next
tmp = prev   # end of first sub list
h2 = cur     # second sub list
if not h2:   # no second sub list, break
break
for x in range(sz):
if not cur:
break
cur = cur.next
prev = prev.next
tmp.next = None  # cut out first sub list
prev.next = None # cut out second sub list
[newH, newT] = self.mergeTwoList(h1, h2)
last.next = newH
newT.next = cur
last = newT  # update tail node of previously merged lists
sz <<= 1
return dummy.next

# merge two sorted list, return [head, tail]
def mergeTwoList(self, h1, h2):
if not h1:
return h2
if not h2:
return h1
dummy = ListNode(0)
c1, c2 = h1, h2
cur = dummy
while c1 or c2:
if c1 and c2:
if c1.val < c2.val:
cur.next = c1
c1 = c1.next
else:
cur.next = c2
c2 = c2.next
elif c1:
cur.next = c1
c1 = c1.next
else:
cur.next = c2
c2 = c2.next
cur = cur.next
return [dummy.next, cur]

def lenList(self, head):
count = 0
while head:
count += 1
head = head.next
return count``````

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