Merge sort is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, meaning that the implementation preserves the input order of equal elements in the sorted output. It is a divide and conquer algorithm. Merge sort was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up mergesort appeared in a report byGoldstine and Neumann as early as 1948
divide and conquer algorithm: 1, split the problem into several subproblem of the same type. 2,solove independetly. 3 combine those solutions
Python Implement
def mergeSort(L):
if len(L) < 2 :
return L
middle = len(L)/2
left = mergeSort(L[:mddle])
right = mergeSort(L[middle:])
together = merge(left,right)
return together