3
\$\begingroup\$

I implemented the linked-list natural merge sort in Python, and I refered 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


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
            return new_head

    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 linked_list_natural_merge_sort(head):
    """Revising from mergesort-linkedlist to Natural_mergesort_linkedlist [1].
    [1]: https://gist.github.com/zed/5651186
    """
    while True:
        p = head
        head, tail = empty, empty 
        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: 
            return head

def mklist(initializer):
    it = reversed(initializer)
    try:
        x = next(it)
    except StopIteration:
        return empty 
    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))

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

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

After reading this answer I modified the linked_list_natural_merge_sort function as follows:

def linked_list_natural_merge_sort(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

Any suggestions or recommendations for further improvements will be highly appreciated. Thanks in advance.

This is the complete code: https://gist.github.com/eduOS/37cf32ed097d487c7ad335148baa4b5f

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.