## Merge Sort

Definition:

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:

• Stable,
• Completed,
• O(n logn) time complexity,
• O ( n ) extra space for arrays,
• O ( logn ) extra space for linked lists,
• Does not require random access data,

How does it work?

In merge sort,

1. Firstly, unsorted array is divided into n sublist, until each sublist has only 1 element,
2. 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

Animation:

For better understanding, go to this animation page.

Pseudocode:

```# 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```

References:

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.

Programming Pearls by Jon Bentley. Addison Wesley, 1986.

http://www.sorting-algorithms.com/merge-sort

Figures from:  http://en.wikipedia.org

For more algorithms, go to Algorithms Section.