Program to implement Merge sort
Merge sort is a sorting algorithm that follows divide and conquer approach .
Algorithm :
MSort(arr[], l, r)If right > l
1. middle m = (left+right)/2
2. Call mSort(arr, left, middle)
3. Call mSort(arr, middle+1, right)
4. repeat step 2 and 3:
Call msort(arr, left, middle, right)
Example :
Program :
def mergeSort(nlist):
print("Splitting ",nlist)
if len(nlist)>1:
mid = len(nlist)//2
lefthalf = nlist[:mid]
righthalf = nlist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=j=k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
nlist[k]=lefthalf[i]
i=i+1
else:
nlist[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
nlist[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
nlist[k]=righthalf[j]
j=j+1
k=k+1
print("Merging ",nlist)
nlist = [1,2,45,23,24,22]
mergeSort(nlist)
print(nlist)
Output :
Splitting [1, 2, 45, 23, 24, 22]
Splitting [1, 2, 45]
Splitting [1]
Merging [1]
Splitting [2, 45]
Splitting [2]
Merging [2]
Splitting [45]
Merging [45]
Merging [2, 45]
Merging [1, 2, 45]
Splitting [23, 24, 22]
Splitting [23]
Merging [23]
Splitting [24, 22]
Splitting [24]
Merging [24]
Splitting [22]
Merging [22]
Merging [22, 24]
Merging [22, 23, 24]
Merging [1, 2, 22, 23, 24, 45]
[1, 2, 22, 23, 24, 45]
For more Rajasthan Technical University CSE VI Sem Python Lab Experiments Click here
| 
| 
