Python: 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."
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:
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 Programming skills with w3resource's quiz.
It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.
https://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-8.php
- Weekly Trends and Language Statistics
- Weekly Trends and Language Statistics