**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,
- 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

**Animation:**

For better understanding, go to this animation page.

**Pseudocode:**

# split in halfm = n / 2# recursive sortssort a[1..m] sort a[m+1..n]# merge sorted sub-arrays using temp arrayb = 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 positionwhile 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.