Several issues:
As you consider h to be the last index of the sublist, then realise that when slicing a list, the second index is the one following the intended range. So change this:
| Wrong |
Right |
l1 = arr[l:m] |
l1 = arr[l:m+1] |
l2 = arr[m+1:h] |
l2 = arr[m+1:h+1] |
As merge returns the result for a sub list, you should not assign it to arr. arr is supposed to be the total list, so you should only replace a part of it:
arr[l:h+1] = merge(arr,l,mid,h)
As the while loop requires that both lists are not empty, you should still consider the case where after the loop one of the lists is still not empty: its elements should be added to the merged result. So replace the return statement to this:
return lis + l1 + l2
It is not advised to compare integers with is or is not, which you do in the while condition. In fact that condition can be simplified to this:
while l1 and l2:
With these changes (and correct indentation) it will work.
Further remarks:
This implementation is not efficient. pop(0) has a O(n) time complexity. Use indexes that you update during the loop, instead of really extracting the values out the lists.
It is more pythonic to let h and m be the indices after the range that they close, instead of them being the indices of the last elements within the range they close. So if you go that way, then some of the above points will be resolved differently.
Corrected implementation
Here is your code adapted using all of the above remarks:
def merge(arr, l, m, h):
lis = []
i = l
j = m
while i < m and j < h:
if arr[i] <= arr[j]:
x = arr[i]
i += 1
else:
x = arr[j]
j += 1
lis.append(x)
return lis + arr[i:m] + arr[j:h]
def merge_sort(arr, l, h):
if l < h - 1:
mid = (l + h) // 2
merge_sort(arr, l, mid)
merge_sort(arr, mid, h)
arr[l:h] = merge(arr, l, mid, h)
return arr
arr = [9, 3, 7, 5, 6, 4, 8, 2]
print(merge_sort(arr,0,len(arr)))
[9,3,7,5,6,4,8,2]is[6,4,8]is not enough. Add someprintstatements in the code to print intermediary results. For instance, addprint('sort: ', arr, l, h)at the beginning ofmerge_sort, andprint('merge: ', arr, l, m, h)at the beginning ofmerge.((len(l1) and len(l2)) is not 0)definitely does not do what you think. Instead, try(len(l1) > 0) and (len(l2) > 0).pop(), not.pop(0). I'd still recommend dealing with the "end" of the list rather than the "beginning" of the list, since popping from the beginning is a very costly operation (when an element is popped, every element after it is "shifted" towards the beginning to fill the gap; if you pop the first element, the whole list is rewritten).