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]