Merge Sort in Python
In computer science merge sort is a most efficient sorting algorithm with time complexity O(nlogn). It famous algorithm to sort elements by using divide and conquer method.
Input:
25 45 30 60 98
Output:
[25,30,45,60,98]
Explanation:
[25 45 30 60 98]
/ \
[25,45] [30,60,98]
/ \ / \
[25] [45] [30] [60,98]
\ / / / \
\ / / [60] [98]
[25,45] [30] [60,98]
\ \ /
\ [30,60,98]
\ /
[25,30,45,60,98] {sorted list}
Code:
def mergeSort(arr):
if len(arr)>1:
mid=len(arr)//2
L=arr[:mid]
R=arr[mid:]
mergeSort(L)
mergeSort(R)
i=j=k=0
while i<len(L) and j<len(R):
if L[i]<R[j]:
arr[k]=L[i]
i+=1
else:
arr[k]=R[j]
j+=1
k+=1
while i<len(L):
arr[k]=L[i]
i+=1
k+=1
while j<len(R):
arr[k]=R[j]
j+=1
k+=1
return arr
array=list(map(int,input().split()))
print(mergeSort(array))
if len(arr)>1:
mid=len(arr)//2
L=arr[:mid]
R=arr[mid:]
mergeSort(L)
mergeSort(R)
i=j=k=0
while i<len(L) and j<len(R):
if L[i]<R[j]:
arr[k]=L[i]
i+=1
else:
arr[k]=R[j]
j+=1
k+=1
while i<len(L):
arr[k]=L[i]
i+=1
k+=1
while j<len(R):
arr[k]=R[j]
j+=1
k+=1
return arr
array=list(map(int,input().split()))
print(mergeSort(array))
Note:
Hello Guys, Don't Stop Learning keep Going..............