# Python Example – Write a Python program to sort a list of elements using the merge sort algorithm # (Python Example for Citizen Data Scientist & Business Analyst)

Write a Python program to sort a list of elements using the merge sort algorithm.

Note: According to Wikipedia “Merge sort (also commonly spelled mergesort) is an O (n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.”

Algorithm:

Conceptually, a merge sort works as follows :

• Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
• Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

An example of merge sort: Sample Solution:

Python 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 = [14,46,43,27,57,41,45,21,70]
mergeSort(nlist)
print(nlist)
``````

Sample Output:

```Splitting  [14, 46, 43, 27, 57, 41, 45, 21, 70]
Splitting  [14, 46, 43, 27]
Splitting  [14, 46]
Splitting  
Merging  
Splitting  
-------
Merging  [14, 21, 27, 41, 43, 45, 46, 57, 70]
[14, 21, 27, 41, 43, 45, 46, 57, 70]```

## Write a Python program to sort a list of elements using the merge sort algorithm

#### Free Machine Learning & Data Science Coding Tutorials in Python & R for Beginners. Subscribe @ Western Australian Center for Applied Machine Learning & Data Science. ```