# Linked-list natural merge sort in Python

I implemented the linked-list natural merge sort in Python, and I referred to this awesome if not poetic gist and this implementation in Go. Here is my code:

# Linked list is either empty or a value and a link to the next list
empty = None # empty list

class LL(object):
__slots__ = "value", "next"
def __init__(self, value, next=empty):
self.value = value
self.next = next

def __le__(self, other):
return self.value <= other.value

def __lt__(self, other):
return self.value < other.value

"""
reference: https://stackoverflow.com/a/22049871/3552
"""

size-=1
if not size:
while tail.next:
tail = tail.next

if next_node is empty:

size = 2

while(next_node.next and next_node <= next_node.next):
size += 1
next_node = next_node.next
next_node = next_node.next
else:
while(next_node.next and next_node.next < next_node):
size += 1
next_node = next_node.next
next_node = next_node.next

: https://gist.github.com/zed/5651186
"""
while True:
nmerges = 0
while p is not empty:
nmerges += 1

q = p
p, psize, next_start, = find_next_stop(p)
q, qsize, next_start = find_next_stop(next_start)

while psize > 0 or (qsize > 0  and q is not empty):
if psize == 0:
e, q = q, q.next
qsize -= 1
elif qsize == 0 or q is empty:
e, p = p, p.next
psize -= 1
elif p.value <= q.value:
e, p = p, p.next
psize -= 1
else: # p.value > q.value i.e., first element of q is lower
e, q = q, q.next
qsize -= 1

# add e to the end of the output list
if tail is not empty:
tail.next = e
else:
head = e # smallest item among two lists
tail = e
p = next_start

if tail is not empty:
tail.next = empty

# if we have done only one merge, we're finished
if nmerges <= 1:

def mklist(initializer):
it = reversed(initializer)
try:
x = next(it)
except StopIteration:
return empty
else:
for value in it:

if size:
size -= 1
else:
break



I tested it as follows:

def test():
for n, r, k in product(range(10), repeat=3):
L = list(range(n)) + [n//2]*r + [n-1]*k
random.shuffle(L)

if __name__ == "__main__":
import random
from itertools import product
test()


def linked_list_natural_merge_sort(head):

: https://gist.github.com/zed/5651186
"""
psize = 0
tail = empty

while q is not empty:
tail = empty
q, qsize, next_q = find_next_stop(q)
msize = psize + qsize

while qsize > 0 or psize > 0:
if psize == 0:
e, q = q, q.next
qsize -= 1
elif qsize == 0:
e, p = p, p.next
psize -= 1
elif p <= q:
e, p = p, p.next
psize -= 1
else:
e, q = q, q.next
qsize -= 1

if tail is empty:
else:
tail.next = e
tail = e

psize = msize
q = next_q