Merge sort is a divide and conquer algorithm. It is a fast, general purpose sorting algorithm.
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]))
[-2, -1, 0, 1, 2, 3, 4]