The algorithm is described on Wikipedia.

Basically it is similar to a merge sort in bottom-up manner. In each stage, I try to find two adjacent non-decreasing "runs" and merge them. We are done if we have only run left.

```
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param two ListNodes
# @return a ListNode
def mergeTwoLists(self, l1, l2):
head = ListNode(0)
tail = head
while True:
if not l1:
tail.next = l2
break
if not l2:
tail.next = l1
break
if l1.val > l2.val:
l1,l2 = l2,l1
tail.next = l1
tail = l1
l1 = l1.next
tail.next = None
while tail.next:
tail = tail.next
return head.next, tail
def findRun(self, head):
if not head:
return None
if not head.next:
return head
last = head
p = head.next
while p:
if p.val < last.val:
break
else:
last = p
p = p.next
return last
def natural_mergesort(self, head):
# calculate the length
n = 0
p = head
while p:
p = p.next
n += 1
# already done
if n <= 1:
return head
while True:
t1 = self.findRun(head)
h1 = head
if not t1.next:
# already sorted
return h1
tail = None
while t1.next:
# we have more than one sublist
h2 = t1.next
t2 = self.findRun(h2)
h3 = t2.next
t1.next = None
t2.next = None
newh, newt = self.mergeTwoLists(h1, h2)
if not tail:
# this is the first pair of runs in this stage
head, tail = newh, newt
else:
tail.next = newh
tail = newt
if not h3:
# no runs any more
h1 = t1 = None
break
else:
h1 = h3
t1 = self.findRun(h3)
if t1:
# we still have one last run
tail.next = h1
tail = t1
# @param head, a ListNode
# @return a ListNode
def sortList(self, head):
return self.natural_mergesort(head)
```