# Python Data Structures and Algorithms: Merge sort

## Python Search and Sorting: Exercise-8 with Solution

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:

**Merge Sort: Pictorial Presentation**

**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 [14] Merging [14] Splitting [46] ------- Merging [14, 21, 27, 41, 43, 45, 46, 57, 70] [14, 21, 27, 41, 43, 45, 46, 57, 70]

**Flowchart: **

## Visualize Python code execution:

The following tool visualize what the computer is doing step-by-step as it executes the said program:

**Python Code Editor :**

** Contribute your code and comments through Disqus.**

**Previous:** Write a Python program to sort a list of elements using shell sort algorithm.

**Next:** Write a Python program to sort a list of elements using the quick sort algorithm.

**What is the difficulty level of this exercise?**

Test your Python skills with w3resource's quiz

## Python: Tips of the Day

**Returns the maximum value of a list, after mapping each element to a value using the provided function**

Example:

def tips_max(lst, fn): return max(map(fn, lst)) print(tips_max([{ 'n': 4 }, { 'n': 2 }, { 'n': 8 }, { 'n': 6 }], lambda v : v['n']))

Output:

8

**New Content published on w3resource :**- Python Numpy exercises
- Python GeoPy Package exercises
- Python Pandas exercises
- Python nltk exercises
- Python BeautifulSoup exercises
- Form Template
- Composer - PHP Package Manager
- PHPUnit - PHP Testing
- Laravel - PHP Framework
- Angular - JavaScript Framework
- React - JavaScript Library
- Vue - JavaScript Framework
- Jest - JavaScript Testing Framework