1

What's wrong with my code? It prints only a part of the vect values. Seems that the while loop breaks at some point. I don't understand why. 

def print_list(vect):
    for i in range(0, len(vect)):
        print(vect[i])

def merge_sort(vect):
    left = []
    right = []    
    result = []

    for i in range(0, int(len(vect)/2)):
        left.append(vect[i])
    for i in range(int(len(vect)/2), len(vect)):
        right.append(vect[i])

    left.sort()
    right.sort()
    i = 0
    j = 0

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

    print(len(result))
    return result

vect = [3, 1, 5, 7, 10, 2, 0]

vect = merge_sort(vect)
Improve this question
1
  • 1
    I don't understand why you're calling left.sort() and right.sort(). That uses Python's internal sorting functions on each half of the list, which makes your implementation of mergesort totally pointless. Commented Feb 8, 2013 at 17:46

2 Answers 2

Reset to default
5

Well, your mistake is that after your while loop

while i < len(left) and j < len(right):
  ...

it may be (and most probably would) that either i < len(left) or j < len(right), so you need to append appropriate part's suffix to the answer. It's easy to do with 

result += left[i:]
result += right[j:]

Explanation:

Imagine the merge procedure: you have i and j at 0 at start, and at every step you move one of them forward. When you stop ? When one of them reaches the end. Let's say i has reached the end. Hereby you added the whole left part to the result, but there are still some elements in right between j and len(right), so you have to add them to the answer too.

Offtop:

You are implementing merge sort, so please have 

left = merge_sort( left )
right = merge_sort( right )

instead of

left.sort()
right.sort()

Attention: you have to add the following check to your code at the beginning of merge function to avoid infinite recursion:

if len( vect ) == 1:
   return vect

Also in your print_list function you can just use

print vect

or at least

for x in vect
print x
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

@user1392136: yes, so it will break when i >= len(left) OR j >= len(right). The other index may still remain less.
so the answer is that I need OR instead of AND there.. if I try with OR, I receive index out of range...
@user1392136: no, the answer is that you need AND, and you need to add the unviewed part of left or right after the while
ah.. I understand.. Thank you. One more thing, if I call left = merge_sort(left) I've receive maximum recursion deep exceeded.
@user1392136: I've edded explanation to this and your previous comment to the answer. Just check if the size of array is 1 to stop the recursion at that point.
3

The while loop exits as soon as either left or right is exhausted. This leaves all the elements left in the unexhausted list unmerged.

Change your code to this:

def print_list(vect):
    for i in range(0, len(vect)):
        print(vect[i])

def merge_sort(vect):
    left = []
    right = []

    result = []
    for i in range(0, int(len(vect)/2)):
        left.append(vect[i])
    for i in range(int(len(vect)/2), len(vect)):
        right.append(vect[i])

    left.sort();
    right.sort();
    i = 0
    j = 0

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

    if i < len(left):
        result.extend(left[i:])
    else:
        result.extend(right[j:])

    print(len(result))
    return result

vect = [3, 1, 5, 7, 10, 2, 0]

vect = merge_sort(vect)
print vect

If you're using the sort method on left and right, I'm a little confused as to why you're not just using it on the list as a whole. But I suppose you have your reasons. :)

Edit: I put the entire block of code there so you can see it. When I run this, it prints [0, 1, 2, 3, 5, 7, 10], which is correct.

Improve this answer

5 Comments

I don't understand why I need to add this at the end of while. However it doesn't works...
I adjusted the answer to be a little more explicit. Maybe it works for you now.
I don't understand why and what I need to extend to make it works... Can you give me some details in words what you do with your new lines of code?
The extend method takes a list as a parameter. It iterates over the list and appends each element to the parent list-like object. What I've done above is to take the remaining parts of each list (that's done using list slice notation [i:] or [j:]) and just add all those remaining elements to the result list.
Can this be considered a true merge sort when it's not recursive? Your calls to left.sort() and right.sort() technically should call back to MergeSort, am I wrong?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.