Understanding Merge and Sort Algorithm in Python

Question

So I'm trying to understand this simple merge and sort algorithm in python. Here's the code:

def merge(left, right, lt):
    """Assumes left and right are sorted lists.

    lt defines an ordering on the elements of the lists.
    Returns a new sorted(by lt) list containing the same elements
    as (left + right) would contain.

    """
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
       if lt(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        while (i < len(left)):
            result.append(left[i])
            i += 1
        while (j < len(right)):
            result.append(right[j])
            j += 1
    return result

def sort(L, lt = lambda x,y: x < y):
    """Returns a new sorted list containing the same elements as L"""
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L)/2)
        left = sort(L[:middle], lt)
        right = sort(L[middle:], lt)
        print left, right
        return merge(left, right, lt)

I get what it's trying to do, and I understand all of the code in the merge function and have a basic understanding of the sort function.

What I don't understand is how the "else" portion of the sort function actually works. It seems like it keeps recursively calling the sort function to assign smaller and smaller split lists to the left and right variables. But since it is assigning new lists to "left" and "right" on every call to the recursive function, won't the end result just be the smallest versions of left and right?

How does the merge function, which seems to lie outside of the recursion, know that it needs to merge every single split list created?

Blender · Accepted Answer · 2012-09-20 20:02:30Z

6

sort() is recursive, but up to a point. The if condition will break the recursion once the length of the list is less than two (or equal to one):

if len(L) < 2:

Wikipedia actually has a nice animation that shows how Merge sort works:

enter image description here

Basically, merge() combines two sorted lists and returns a single sorted list. sort() recursively breaks up your list into pairs and sorts the pairs one step at a time, merging two sorted pairs to form a larger sorted list at every step in the recursion. Just watch the animation. It's better at explaining than I am.

edited Sep 20, 2012 at 20:02

answered Sep 20, 2012 at 19:55

Blender

300k55 gold badges462 silver badges511 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Dan W Over a year ago

I watched that entire animation.

user1427661 Over a year ago

Okay, so now I get that at the end of the function, merge is called to sort the pair. But how does the function continue after that to keep sorting the pairs, as shown in the image above? It seems like the function would simply end after merge is returned.

Blender Over a year ago

You have to wrap your head around recursion because you're calling sort from within sort. Past the first split of the large list, all those small steps are being performed in the recursion as each of those larger lists is being split in half and worked on. Try manually unraveling the recursion for a trivial list [2, 1] and then [2, 3, 1].

Kris Harper · Accepted Answer · 2012-09-20 19:56:30Z

3

You should draw out the call stack and see what happens.

When the else clause calls the sort functions again, the function doesn't exit there. Every call ends in one of the return statements.

So you're correct that initially the calls to sort are passed in smaller and smaller lists, but once the length becomes less than 2, 'sort' returns the list itself. Then the call returns to where it was and calls print and finally merge.

Try using a small list and write down every call. You'll see that eventually merge does get called on small lists which have been sorted (since they're so short).

answered Sep 20, 2012 at 19:56

Kris Harper

5,9229 gold badges56 silver badges102 bronze badges

Collectives™ on Stack Overflow

Understanding Merge and Sort Algorithm in Python

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related