# Merge Sort in Python

Third in my series of dives into sorting algorithms is merge sort. Please see bubble sort and selection sort for my previous entries.

### Example

```
import pytest
def merge_sort(to_sort: list):
if not isinstance(to_sort, list):
return to_sort
if len(to_sort) < 2:
return to_sort
mid_point: int = len(to_sort) // 2
left: list = to_sort[:mid_point]
merge_sort(left)
right: list = to_sort[mid_point:]
merge_sort(right)
for i in range(len(to_sort)):
print(to_sort)
if left and right and left[0] <= right[0]:
to_sort[i] = left.pop(0)
elif not right:
to_sort[i] = left.pop(0)
else:
to_sort[i] = right.pop(0)
return to_sort
test_data = [
(None, None),
([], []),
([1, 2, 3], [1, 2, 3]),
([3, 2, 1], [1, 2, 3]),
([-1, -5, -2, -4], [-5, -4, -2, -1]),
([0, 1, 0, -3, 999, 0, -1], [-3, -1, 0, 0, 0, 1, 999])
]
@pytest.mark.parametrize("input,expected", test_data)
def test_merge_sort(input, expected):
assert merge_sort(input) == expected
```

### What is merge sort

Merge sort is a comparison-based sorting algorithm that follows the divide and conquer strategy. It divides the unsorted list into 2 halves, and then recursively splits those halves again until they can be split not further. Then it works its way back up the list, sorting the results of re-combining the lists as it goes.

I was keen to dig into merge sort as unlike bubble and selection sort, it is a sorting algorithm with real-world application. It has a time complexity of O(n ∗ log n), and a space complexity of O(n). Much improved on the O(n^2) of bubble and selection sort!

In fact, it forms the basis for timsort which is a popular sorting algorithm which is used by many languages base libraries such as Python and Java.