merge_sort.py

defmerge_sort(array):
# derive the mid-point
iflen(array) >1:
mid=len(array) //2

# create the temp sub-arrays
LEFT=array[:mid]
RIGHT=array[mid:]

# sort the first and second halves
merge_sort(LEFT)
merge_sort(RIGHT)

# begin addig elements in sorted order
i, j, k=0, 0, 1

whilei<len(LEFT) andj<len(RIGHT):
ifLEFT[i] <RIGHT[j]:
array[k] =LEFT[i]
i+=1
else:
array[k] =RIGHT[j]
j+=1
k+=1

# copy the remaining data
whilei<len(LEFT):
array[k] =LEFT[i]
i+=1
k+=1

whilej<len(RIGHT):
array[k] =RIGHT[j]
j+=1
k+=1


arr= [6, 5, 3, 1, 8, 7, 2, 4]
merge_sort(arr)
print(arr)