My implementation:
def merge_sort(arr):
if len(arr) <= 1:
return arr
left = arr[:len(arr)//2]
right = arr[len(arr)//2:]
merge_sort(left)
merge_sort(right)
return merge(left, right)
def merge(left, right):
leftI = rightI = 0
merged = []
while (leftI < len(left) and rightI < len(right)):
if left[leftI] < right[rightI]:
merged.append(left[leftI])
leftI += 1
else:
merged.append(right[rightI])
rightI += 1
merged.extend(left[leftI:])
merged.extend(right[rightI:])
return merged
if __name__ == '__main__':
arr = [1,2,5,5,9,22,6,3,6,8,1,43,5]
print(merge_sort(arr))
For some reason I am obtaining:
[1, 2, 5, 5, 6, 3, 6, 8, 1, 9, 22, 43, 5]
Working Implementation (Got from a friend):
def merge_sort(list):
list_length = len(list)
if list_length == 1:
return list
mid_point = list_length // 2
left_partition = merge_sort(list[:mid_point])
right_partition = merge_sort(list[mid_point:])
return merge(left_partition, right_partition)
def merge(left, right):
output = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
output.append(left[i])
i += 1
else:
output.append(right[j])
j += 1
output.extend(left[i:])
output.extend(right[j:])
return output
if __name__ == '__main__':
arr = [1,2,5,5,9,22,6,3,6,8,1,43,5]
print(merge_sort(arr))
This code yeilds:
[1, 1, 2, 3, 5, 5, 5, 6, 6, 8, 9, 22, 43]
I just can't figure out what's wrong. It'd be a great help if someone could take a few moments to help me out :)
In your merge_sort function, you do not change the values of left and right depending on what merge_sort returns.
You have :
merge_sort(left)
merge_sort(right)
Where it should be :
left = merge_sort(left)
right = merge_sort(right)