Merge Sort is a type of sorting algorithm. It is a divide and conquer algorithm and it was invented by John von Neumann.
In worst, average and best case its time complexity is O(n logn).
Its Properties in short:
- O(n logn) time complexity,
- O ( n ) extra space for arrays,
- O ( logn ) extra space for linked lists,
- Does not require random access data,
- Not adaptive.
How does it work?
In merge sort,
- Firstly, unsorted array is divided into n sublist, until each sublist has only 1 element,
- Then all elements are merged according to their value and new sorted arrays are created.
In the figure below, you can see animated merge sort example.
Animated Merge Sort Example
Another example for merge sort is:
Example For Merge Sort
For better understanding, go to this animation page.
# split in half m = n / 2 # recursive sorts sort a[1..m] sort a[m+1..n] # merge sorted sub-arrays using temp array b = copy of a[1..m] i = 1, j = m+1, k = 1 while i <= m and j <= n, a[k++] = (a[j] < b[i]) ? a[j++] : b[i++] → invariant: a[1..k] in final position while i <= m, a[k++] = b[i++] → invariant: a[1..k] in final position
Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.
Programming Pearls by Jon Bentley. Addison Wesley, 1986.
Figures from: http://en.wikipedia.org
For more algorithms, go to Algorithms Section.