In computer science, merge sort or mergesort is an O(n log n) comparison-based sorting algorithm. It is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It was invented by John von Neumann in 1945.
Algorithm
Conceptually, merge sort works as follows:
Divide the unsorted list into two sublists of about half the size
Divide each of the two sublists recursively until we have list sizes of length 1, in which case the list itself is returned
Merge the two sublists back into one sorted list.
Mergesort incorporates two main ideas to improve its runtime:
A small list will take fewer steps to sort than a large list.
Fewer steps are required to construct a sorted list from two sorted lists than two unsorted lists. For example, you only have to traverse each list once if they're already sorted.
Reference:
http://en.wikipedia.org/wiki/Merge_sort
