# Merge Sort in Python

By Gaurav Jain on February 10, 2018

Merge sort is an O(n log n) divide-and-conquer sorting algorithm.

The idea is to split the the input list/array into two halves, repeating the process on those halves, and merge the two sorted halves together again.

You can visualize the process below -

```
[17, 87, 62, 55, 42, 42, 5, 37, 50, 88]
[17, 87, 62, 55, 42] [42, 5, 37, 50, 88]
[17, 87] [62, 55, 42] [42, 5] [37, 50, 88]
[17] [87] [62] [55, 42] [42] [5] [37] [50, 88]
[17] [87] [62] [55] [42] [42] [5] [37] [50] [88]
[17] [87] [62] [42, 55] [42] [5] [37] [50, 88]
[17, 87] [42, 55, 62] [5, 42] [37, 50, 88]
[17, 42, 55, 62, 87] [5, 37, 42, 50, 88]
[5, 17, 37, 42, 42, 50, 55, 62, 87, 88]
```

```
def merge_sort(alist):
"""
Sort the array using merge sort algorithm
>>> mylist = [17, 87, 62, 55, 42, 42, 5, 37, 50, 88]
>>> merge_sort(mylist)
[5, 17, 37, 42, 42, 50, 55, 62, 87, 88]
>>>
"""
if len(alist) > 1:
mid = len(alist) // 2 # Mid of the array
left_list = alist[:mid] # Creating another list for first half
right_list = alist[mid:] # Creating another list for second half
merge_sort(left_list) # Sorting the left list recursively
merge_sort(right_list) # Sorting the right list recursively
i = j = k = 0
while i < len(left_list) and j < len(right_list):
if left_list[i] < right_list[j]:
alist[k] = left_list[i]
i += 1
else:
alist[k] = right_list[j]
j += 1
k += 1
# Remaining elements
while i < len(left_list):
alist[k] = left_list[i]
i += 1
k += 1
while j < len(right_list):
alist[k] = right_list[j]
j += 1
k += 1
```

Usage:

```
>>> mylist = [17, 87, 62, 55, 42, 42, 5, 37, 50, 88]
>>> merge_sort(mylist)
>>> mylist
[5, 17, 37, 42, 42, 50, 55, 62, 87, 88]
>>>
```

##
This code can be found on *Github [Python-DSA]*.

*If you find anything wrong or has a better solution, please feel free to create issues on this repo.*