[Solved] Merge Sort Python 2.7x

by


The issue is that with the line

arr = ls + rs

You are no longer calling merge on the list passed to merge_sort, but rather calling it on a copy. So the original list isn’t being modified. To correct this issue you can have the merge_sort function return arr at the end, then assign ls = merge_sort(ls) (and similar for rs). Having done that your code should work.

the correct version is here..

def merge_sort(arr):
  def merge(sub_arr,p,q):
    L = []
    R = []
    for i in range(p):
        L.append(sub_arr[i])
    for i in range(q-p):
        R.append(sub_arr[p+i])
    L.append('n')
    R.append('n')
    j=k=0
    for i in range(q):
        if L[j] < R[k] :
            sub_arr[i] = L[j]
            j += 1
        else:
            sub_arr[i] = R[k]
            k += 1
  if len(arr) > 1 :
    ls = arr[:len(arr)/2]
    rs = arr[len(arr)/2:]
    ls = merge_sort(ls)
    rs = merge_sort(rs)    
    arr = ls + rs
    merge (arr,len(arr)/2,len(arr))
  return arr

This gives the expected result

>>> x = map(int,raw_input('Enter sequence:').strip().split())
Enter sequence:4 5 2 1 3 4 6
>>> y = merge_sort(x)
>>> print x
[4, 5, 2, 1, 3, 4, 6]
>>> print y
[1, 2, 3, 4, 4, 5, 6]

1

solved Merge Sort Python 2.7x