Hello everyone, welcome back to Programming In Python. Here in this post am going to tell you how to implement Merge Sort Algorithm in Python. In the previous posts, I have said about Selection Sort and Bubble Sort, here this Merge sort is much more efficient than those two algorithms as their time complexity is O(n^{2}) in the average case and here it is O(n log n) in the worst case, this says how efficient Merge sort is than Selection and Bubble sort.

Merge sort algorithm is a divide and conquer algorithm, where the main unsorted list is divided into 2 halves, and each of the halves is again divided into 2 halves until only a single element is left in the list. Now merge these sublists by sorting them and finally, the main list is sorted.

**You can also watch the video on YouTube here**

See the animation below,

By Swfung8 – Own work, CC BY-SA 3.0, Link

#### Time Complexity Of Merge Sort

Best Case |
O(n log n) |

Average Case |
O(n log n) |

Worst Case |
O(n log n) |

## Algorithm

- Divide the unsorted list into
*n*sublists, until each list has only 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.

## Merge Sort Algorithm – Code Visualization

## Program

__author__ = 'Avinash' def merge_sort(sort_list): print("splitting", sort_list) if len(sort_list) > 1: mid = len(sort_list) // 2 leftHalf = sort_list[:mid] rightHalf = sort_list[mid:] merge_sort(leftHalf) merge_sort(rightHalf) i = 0 j = 0 k = 0 while i < len(leftHalf) and j < len(rightHalf): if leftHalf[i] < rightHalf[j]: sort_list[k] = leftHalf[i] i = i + 1 else: sort_list[k] = rightHalf[j] j = j + 1 k = k + 1 while i < len(leftHalf): sort_list[k] = leftHalf[i] i = i + 1 k = k + 1 while j < len(rightHalf): sort_list[k] = rightHalf[j] j = j + 1 k = k + 1 print("merging...", sort_list) lst = [] size = int(input("Enter size of the list: \t")) for i in range(size): elements = int(input("Enter an element: \t")) lst.append(elements) merge_sort(lst)

Ad:

Learn Python Programming Masterclass – Enroll Now.

Udemy

## Output

Also, feel free to look at other sorting algorithms like Bubble Sort or Selection Sort and searching algorithms like Linear Search and Binary Search.