Reputation: 1788
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)
Upvotes: 1
Views: 1052
Reputation: 6853
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
Upvotes: 5
Reputation: 33
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.
Upvotes: 3