Skip to content

Instantly share code, notes, and snippets.

@zed

zed/mergesort-linkedlist.py

Last active July 30, 2022 00:28
Show Gist options
  • Save zed/5651186 to your computer and use it in GitHub Desktop.
Save zed/5651186 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. zed revised this gist May 25, 2013. 1 changed file with 8 additions and 1 deletion.
    9 changes: 8 additions & 1 deletion mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -28,7 +28,14 @@ def llistsort(head):
    [2]: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
    """
    insize = 1 # lists of size 1 are always sorted
    while True: # merge adjacent pairs of `insize`-sized lists
    while True: # merge adjacent pairs of `insize`-sized sorted lists
    if __debug__: # check the loop invariant
    pairwise = lambda L: zip(L, L[1:])
    issorted = lambda L: all(x <= y for x, y in pairwise(L))
    # all adjacent `insize`-sized lists are sorted
    lst = tolist(head)
    assert all(issorted(lst[i:i+insize])
    for i in range(0, len(lst), insize))
    p = head # head of the left list to be merged
    head, tail = empty, empty # head and tail of the output list
    nmerges = 0 # count number of merges we do in this pass
  2. zed revised this gist May 25, 2013. 1 changed file with 11 additions and 3 deletions.
    14 changes: 11 additions & 3 deletions mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -15,8 +15,14 @@ def __init__(self, value, next=empty):
    def llistsort(head):
    """Translation from C to Python of listsort() [1].
    O(N log N) (best, average, worst) -time (Mergesort), O(1)-space
    inplace sorting algorithm for a singly linked linear list [2]
    O(N log N) (best & worst) -time, O(1)-space
    inplace Mergesort algorithm for a singly linked linear list [2]
    >>> head = mklist([2, 3, 1])
    >>> tolist(head)
    [2, 3, 1]
    >>> tolist(llistsort(head))
    [1, 2, 3]
    [1]: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c
    [2]: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
    @@ -105,4 +111,6 @@ def test():
    head = llistsort(head)
    assert tolist(head) == sorted(L)

    test()
    if __name__ == "__main__":
    import doctest; doctest.testmod()
    test()
  3. zed revised this gist May 25, 2013. 1 changed file with 23 additions and 22 deletions.
    45 changes: 23 additions & 22 deletions mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -5,32 +5,13 @@

    # 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 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):
    while head is not empty:
    yield head.value
    head = head.next

    def tolist(head):
    return list(walk(head))

    def llistsort(head):
    """Translation from C to Python of listsort() [1].
    @@ -95,13 +76,33 @@ def llistsort(head):
    else:# otherwise repeat, merging lists twice the size
    insize *= 2

    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):
    while head is not empty:
    yield head.value
    head = head.next

    def tolist(head):
    return list(walk(head))

    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)
    result = tolist(head)
    assert result == sorted(L)
    assert tolist(head) == sorted(L)

    test()
  4. zed revised this gist May 25, 2013. 1 changed file with 14 additions and 14 deletions.
    28 changes: 14 additions & 14 deletions mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -3,11 +3,11 @@
    import random
    from itertools import product

    # Linked list is either None (empty list) or a value and a link to the
    # next list
    # 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=None):
    def __init__(self, value, next=empty):
    self.value = value
    self.next = next

    @@ -16,15 +16,15 @@ def mklist(initializer):
    try:
    x = next(it)
    except StopIteration:
    return None # empty list is None
    return empty # empty list
    else:
    head = LL(x)
    for value in it:
    head = LL(value, head)
    return head

    def walk(head):
    while head is not None:
    while head is not empty:
    yield head.value
    head = head.next

    @@ -43,28 +43,28 @@ def llistsort(head):
    insize = 1 # lists of size 1 are always sorted
    while True: # merge adjacent pairs of `insize`-sized lists
    p = head # head of the left list to be merged
    head, tail = None, None # head and tail of the output list
    head, tail = empty, empty # head and tail of the output list
    nmerges = 0 # count number of merges we do in this pass
    while p is not None:
    while p is not empty:
    nmerges += 1 # there exists a merge to be done

    # step `insize' places along from p or until the end of
    # the list, whichever comes first
    q = p # head of the right list to be merged
    for psize in range(1, insize + 1):
    q = q.next
    if q is None: # the end of the list (q is empty list)
    if q is empty: # the end of the list (q is empty list)
    break
    qsize = insize

    # merge a list starting at p, of length psize, with a list
    # starting at q of length *at most* qsize
    while psize > 0 or (qsize > 0 and q is not None):
    while psize > 0 or (qsize > 0 and q is not empty):
    # decide whether next element of merge comes from p or q
    if psize == 0: # p is empty
    e, q = q, q.next # e must come from q, pop q
    qsize -= 1
    elif qsize == 0 or q is None: # q is empty
    elif qsize == 0 or q is empty: # q is empty
    e, p = p, p.next # e must come from p, pop p
    psize -= 1
    elif p.value <= q.value: # first element of p is lower or same
    @@ -77,17 +77,17 @@ def llistsort(head):
    qsize -= 1

    # add e to the end of the output list
    if tail is not None:
    if tail is not empty:
    tail.next = e
    else: # 1st iteration
    head = e # smallest item among two lists
    tail = e
    # now p has stepped `insize' places along, and q has too (or eol)
    p = q # move to the next pair of lists to merge
    #end of while p is not None:
    #end of while p is not empty:

    if tail is not None:
    tail.next = None # terminate the output list
    if tail is not empty:
    tail.next = empty # terminate the output list

    # if we have done only one merge, we're finished
    if nmerges <= 1: # allow for nmerges==0, the empty list case
  5. zed revised this gist May 25, 2013. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -96,7 +96,7 @@ def llistsort(head):
    insize *= 2

    def test():
    for n, r, k in product(range(14), repeat=3):
    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)
  6. zed revised this gist May 25, 2013. 1 changed file with 37 additions and 24 deletions.
    61 changes: 37 additions & 24 deletions mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,6 +1,10 @@
    #!/usr/bin/env python
    """Merge sort a singly linked linear list."""
    import random
    from itertools import product

    # Linked list is either None (empty list) or a value and a link to the
    # next list
    class LL(object):
    __slots__ = "value", "next"
    def __init__(self, value, next=None):
    @@ -27,67 +31,76 @@ def walk(head):
    def tolist(head):
    return list(walk(head))

    def listsort(head):
    def llistsort(head):
    """Translation from C to Python of listsort() [1].
    O(N log N) (best, average, worst) -time (Mergesort), O(1)-space
    inplace sorting algorithm for a singly linked linear list [2]
    [1]: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c
    [2]: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html
    """
    insize = 1
    while True:
    p = head
    head, tail = None, None # head and tail of merged list
    insize = 1 # lists of size 1 are always sorted
    while True: # merge adjacent pairs of `insize`-sized lists
    p = head # head of the left list to be merged
    head, tail = None, None # head and tail of the output list
    nmerges = 0 # count number of merges we do in this pass
    while p is not None:
    nmerges += 1 # there exists a merge to be done

    # step `insize' places along from p
    q = p
    # step `insize' places along from p or until the end of
    # the list, whichever comes first
    q = p # head of the right list to be merged
    for psize in range(1, insize + 1):
    q = q.next
    if q is None:
    if q is None: # the end of the list (q is empty list)
    break
    qsize = insize

    # if q hasn't fallen off end, we have two lists to merge
    # merge a list starting at p, of length psize, with a list
    # starting at q of length *at most* qsize
    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, q = q, q.next # e must come from q
    e, q = q, q.next # e must come from q, pop q
    qsize -= 1
    elif qsize == 0 or q is None: # q is empty
    e, p = p, p.next # e must come from p
    e, p = p, p.next # e must come from p, pop p
    psize -= 1
    elif p.value <= q.value: # first element of p is lower (or same)
    e, p = p, p.next # e must come from p
    elif p.value <= q.value: # first element of p is lower or same
    # choose p in the case of `p.value == q.value` to
    # maintain sort stability
    e, p = p, p.next # e must come from p, pop p
    psize -= 1
    else: # p.value > q.value i.e., first element of q is lower
    e, q = q, q.next # e must come from q
    e, q = q, q.next # e must come from q, pop q
    qsize -= 1

    # add the next element to the merged list
    # add e to the end of the output list
    if tail is not None:
    tail.next = e
    else:
    head = e

    else: # 1st iteration
    head = e # smallest item among two lists
    tail = e
    # now p has stepped `insize' places along, and q has too
    p = q
    # now p has stepped `insize' places along, and q has too (or eol)
    p = q # move to the next pair of lists to merge
    #end of while p is not None:

    if tail is not None:
    tail.next = None
    tail.next = None # terminate the output list

    # 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
    else:# 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)
    head = llistsort(head)
    result = tolist(head)
    assert result == sorted(L)

  7. zed revised this gist May 25, 2013. 1 changed file with 16 additions and 20 deletions.
    36 changes: 16 additions & 20 deletions mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -35,37 +35,33 @@ def listsort(head):
    insize = 1
    while True:
    p = head
    head, tail = None, None
    head, tail = None, None # head and tail of merged list
    nmerges = 0 # count number of merges we do in this pass
    while p:
    while p is not None:
    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

    # step `insize' places along from p
    q = p
    for psize in range(1, insize + 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

    # if q hasn't fallen off end, we have two lists to merge
    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
    if psize == 0: # p is empty
    e, q = q, q.next # e must come from q
    qsize -= 1
    elif qsize == 0 or q is None:
    # q is empty; e must come from p
    e, p = p, p.next
    elif qsize == 0 or q is None: # q is empty
    e, p = p, p.next # e must come from p
    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
    elif p.value <= q.value: # first element of p is lower (or same)
    e, p = p, p.next # e must come from p
    psize -= 1
    else:
    # first element of q is lower; e must come from q
    e, q = q, q.next
    else: # p.value > q.value i.e., first element of q is lower
    e, q = q, q.next # e must come from q
    qsize -= 1

    # add the next element to the merged list
  8. zed revised this gist May 25, 2013. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -1,4 +1,5 @@
    import random
    from itertools import product

    class LL(object):
    __slots__ = "value", "next"
  9. zed revised this gist May 25, 2013. 1 changed file with 2 additions and 4 deletions.
    6 changes: 2 additions & 4 deletions mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -31,9 +31,6 @@ def listsort(head):
    [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
    @@ -80,7 +77,8 @@ def listsort(head):
    # now p has stepped `insize' places along, and q has too
    p = q

    tail.next = None
    if tail is not None:
    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
  10. zed revised this gist May 25, 2013. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -88,8 +88,8 @@ def listsort(head):
    insize *= 2

    def test():
    for L in [list(range(13)), [], [1]*3,
    list(range(13)) + [1]*3]:
    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)
  11. zed created this gist May 25, 2013.
    99 changes: 99 additions & 0 deletions mergesort-linkedlist.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,99 @@
    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 L in [list(range(13)), [], [1]*3,
    list(range(13)) + [1]*3]:
    random.shuffle(L)
    head = mklist(L)
    head = listsort(head)
    result = tolist(head)
    assert result == sorted(L)

    test()