Last active
July 30, 2022 00:28
-
-
Save zed/5651186 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import random | |
| class LL(object): | |
| __slots__ = "value", "next" | |
| def __init__(self, value, next=None): | |
| self.value = value | |
| self.next = next | |
| def mklist(initializer): | |
| it = reversed(initializer) | |
| try: | |
| x = next(it) | |
| except StopIteration: | |
| return None # empty list is None | |
| else: | |
| head = LL(x) | |
| for value in it: | |
| head = LL(value, head) | |
| return head | |
| def walk(head): | |
| while head is not None: | |
| yield head.value | |
| head = head.next | |
| def tolist(head): | |
| return list(walk(head)) | |
| def listsort(head): | |
| """Translation from C to Python of listsort() [1]. | |
| [1]: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c | |
| """ | |
| if head is None: # empty list is already sorted | |
| return head | |
| insize = 1 | |
| while True: | |
| p = head | |
| head, tail = None, None | |
| nmerges = 0 # count number of merges we do in this pass | |
| while p: | |
| nmerges += 1 # there exists a merge to be done | |
| q = p # step `insize' places along from p | |
| psize = 0 | |
| for _ in range(insize): | |
| psize += 1 | |
| q = q.next | |
| if q is None: | |
| break | |
| # if q hasn't fallen off end, we have two lists to merge | |
| qsize = insize | |
| # now we have two lists; merge them | |
| while psize > 0 or (qsize > 0 and q is not None): | |
| # decide whether next element of merge comes from p or q | |
| if psize == 0: | |
| # p is empty; e must come from q | |
| e, q = q, q.next | |
| qsize -= 1 | |
| elif qsize == 0 or q is None: | |
| # q is empty; e must come from p | |
| e, p = p, p.next | |
| psize -= 1 | |
| elif p.value <= q.value: | |
| # first element of p is lower (or same); e must come from p | |
| e, p = p, p.next | |
| psize -= 1 | |
| else: | |
| # first element of q is lower; e must come from q | |
| e, q = q, q.next | |
| qsize -= 1 | |
| # add the next element to the merged list | |
| if tail is not None: | |
| tail.next = e | |
| else: | |
| head = e | |
| tail = e | |
| # now p has stepped `insize' places along, and q has too | |
| p = q | |
| tail.next = None | |
| # if we have done only one merge, we're finished | |
| if nmerges <= 1: # allow for nmerges==0, the empty list case | |
| return head | |
| # otherwise repeat, merging lists twice the size | |
| insize *= 2 | |
| def test(): | |
| for n, r, k in product(range(14), repeat=3): | |
| L = list(range(n)) + [n//2]*r + [n-1]*k | |
| random.shuffle(L) | |
| head = mklist(L) | |
| head = listsort(head) | |
| result = tolist(head) | |
| assert result == sorted(L) | |
| test() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment