# Merge Sort

0
26

Merge Sort is a divide-and-conquer algorithm. It divides the input list of length n in half successively until there are n lists of size 1. Then, pairs of lists are merged together with the smaller ﬁrst element among the pair of lists being added in each step. Through successive merging and through comparison of ﬁrst elements, the sorted list is built.

## Merge Sort Basics

See bellow picture to undertand how merge sort work:

Time Complexity: `T(n) = 2T(n/2) + Θ(n)`

The above recurrence can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is Θ(nLogn). Time complexity of Merge Sort is `Θ(nLogn)` in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.

Auxiliary Space: `O(n)`

Algorithmic Paradigm: Divide and Conquer

Sorting In Place: Not in a typical implementation

Stable: Yes

## Merge Sort Explained

See bellow merge sort animation to see how merge sort work in step-by-step, source: Wikipedia.

Video expalained

Watch video tutorial help you easy to understand merge sort algorithm. These videos will be very useful for you.

Or this video:

## Merge Sort Implementation

We are going to implement merge sort in several programing languages:

### Merge Sort implementation in Java

Below there is the implementation in Java using a generics approach. It is the same algorithm, which is presented above.

Bottoms-up Java Implementation:

### Python implementation

You may also like:

This site uses Akismet to reduce spam. Learn how your comment data is processed.