Hello everyone, welcome back to programminginpython.com. 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 average case and here it is O(n log n) in 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 single element is left in the list. Now merging 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
__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) |

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