Merge sort is a divide and conquer algorithm. It is a fast, general purpose sorting algorithm.

Time complexity:

Average case : **O(n log n)**

Best case : **O(n log n)**

Worst case : **O(n log n)**

Worst case space complexity : **O(n)**

It works as follows :

If the length of the list is 0 or 1, it is considered as sorted.

The unsorted list is divided into two lists of approximately the same size.

Each list (left and right) is sorted recursively by re-applying the merge sort algorithm.

Once both the left and right lists are sorted they are merged to produce a sorted list

Implementation in Python :

```
def mergesort(list):
if len(list) < 2:
return list
mid = int(len(list)/2)
left = mergesort(list[:mid])
right = mergesort(list[mid:])
return merge(left, right)
def merge(left, right):
result = list()
il = 0
ir = 0
for ix in range(len(left) + len(right)):
if il < len(left) and ir < len(right):
if left[il] <= right[ir]:
result.append(left[il])
il += 1
else:
result.append(right[ir])
ir += 1
elif ir >= len(right):
result.append(left[il])
il += 1
else:
result.append(right[ir])
ir += 1
return result
if __name__ == "__main__":
print(mergesort([3,2,1,4,-1,-2,0]))
```

Output:

```
[-2, -1, 0, 1, 2, 3, 4]
```

Links: