# Write a Program to implement Merge sort

0 like 0 dislike
613 views
Write a Program to implement Merge sort
 Where can I do online courses From Word's Top Instructors? UDEMY:: Attend All Udemy Courses in Just INR 450[Coupon] Coursera:: Join For FREE

0 like 0 dislike
by Goeduhub's Expert (7.6k points)
edited

## 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 

Merging 

Splitting [2, 45]

Splitting 

Merging 

Splitting 

Merging 

Merging [2, 45]

Merging [1, 2, 45]

Splitting [23, 24, 22]

Splitting 

Merging 

Splitting [24, 22]

Splitting 

Merging 

Splitting 

Merging 

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 