# Python Program to perform merge sort

0 like 0 dislike
1.6k views
Python Program to perform merge sort

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

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 Code

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 = [23,47,83,13,56,69]

mergeSort(nlist)

print("Sorted list:",nlist)

Output

Splitting: [23, 47, 83, 13, 56, 69]

Splitting: [23, 47, 83]

Splitting: [23]

Merging: [23]

Splitting: [47, 83]

Splitting: [47]

Merging: [47]

Splitting: [83]

Merging: [83]

Merging: [47, 83]

Merging: [23, 47, 83]

Splitting: [13, 56, 69]

Splitting: [13]

Merging: [13]

Splitting: [56, 69]

Splitting: [56]

Merging: [56]

Splitting: [69]

Merging: [69]

Merging: [56, 69]

Merging: [13, 56, 69]

Merging: [13, 23, 47, 56, 69, 83]

Sorted list: [13, 23, 47, 56, 69, 83]

## For more RGPV/UTMP CSE V Sem Python Lab Experiments Click here

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.