Skip to content

Instantly share code, notes, and snippets.

@eduOS
Forked from zed/mergesort-linkedlist.py
Last active January 13, 2019 02:04
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save eduOS/37cf32ed097d487c7ad335148baa4b5f to your computer and use it in GitHub Desktop.
#!/usr/bin/env python
"""Natural-Merge sort a singly linked linear list."""
import random
from itertools import product
# 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
def reverse(head, size=-1):
"""
reference: https://stackoverflow.com/a/22049871/3552
"""
new_head = None
while head:
temp = head
head = temp.next
temp.next = new_head
new_head = temp
size-=1
if not size:
tail = new_head
while tail.next:
tail = tail.next
tail.next = head
break
return new_head
def find_next_stop(head):
if head is empty:
return head, 0, empty
next_node = head.next
if next_node is empty:
return head, 1, empty
size = 2
if head <= next_node:
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
head = reverse(head, size)
return head, size, next_node
def llistsort(head):
"""Revising from mergesort-linkedlist to Natural_mergesort_linkedlist [1].
[1]: https://gist.github.com/zed/5651186
"""
p = q = head
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:
head = e
else:
tail.next = e
tail = e
psize = msize
q = next_q
p = head
if tail is not empty:
tail.next = empty
return head
def mklist(initializer):
it = reversed(initializer)
try:
x = next(it)
except StopIteration:
return empty # empty list
else:
head = LL(x)
for value in it:
head = LL(value, head)
return head
def walk(head, size=-1):
while head is not empty:
if size:
size -= 1
else:
break
yield head.value
head = head.next
def tolist(head, size=-1):
return list(walk(head, size))
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)
head = mklist(L)
assert tolist(head) == L
head = llistsort(head)
assert tolist(head) == sorted(L)
if __name__ == "__main__":
# import doctest; doctest.testmod()
# any futher improvements will be highly appreciated: https://codereview.stackexchange.com/q/211149/77243
test()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment