w3resource

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."

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 animation

Merge Sort: Pictorial Presentation

Pictorial Presentation: 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  [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:

Flowchart: Python Data Structures and Algorithms: Merge sort

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.



Follow us on Facebook and Twitter for latest update.