Krishnakanth Jc Krishnakanth Jc - 3 months ago 6
Python Question

Merge Sort not happening correctly - Python

Sorting is not happening correctly. Can some one help on sorting with this approach. Also please let me know where I am going wrong. I am new to Python so I am doing this myself. I am using the usual approach as we do in C or other languages.

base =[5,4,3,2,1]

def splitarray (low, high):
if low < high:
mid = (high+low)/2

splitarray (low, mid)
splitarray (mid+1,high)
merge(low,mid,high)

else:
return

def merge(low,mid,high):
print("merge " +str(low) + " - " +str(mid)+" - "+ str(high))
result = [0]*len(base)
k = 0
i=low
j=mid+1
l=0


while i <= mid and j <= high:
if (base[i] < base[j]):

result[k]= base[i]
k+=1
i += 1

if (base[i] > base[j]) :


result[k]= base[j]

j += 1
k += 1





while i <= mid:
result[k]= base[i]
k += 1
i += 1
while j <= high:
result[k]= base[j]
#count = count + mid - i
j += 1
k += 1

print result

l = low
k= 0
while l <= high:
base[l] = result[l]
l += 1


print base
splitarray(0,len(base)-1)

Answer

The issue with your current (updated) code appears to be with the last loop:

l = low
k= 0
while l <= high:
    base[l] = result[l]
    l += 1

Here you're copying the values from the results list to the base list. However, the results are all at the start of results, not at the same coordinates you want them to go in base. You seem to have almost got it right since you're setting k to zero, but you don't end up using k in the loop.

Try:

l = low
k= 0
while l <= high:
    base[l] = result[k]  # read the result from index k, not l
    l += 1
    k += 1  # increment k as well

This should work as intended. Note that while this will do the sorting correctly, this isn't a very elegant way of sorting in Python. To start with, you can only sort the one global variable base, not any list (it would be much nicer to pass the list as a parameter). However, since this looks like something you've written mostly for the learning experience, I'll leave further improvements up to you.