Merge Sort

Merge Sort Algorithm with explained
Merge Sort Algorithm with explained

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 first element among the pair of lists being added in each step. Through successive merging and through comparison of first 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.

How merge sort work with animation explained
How merge sort work with animation explained

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 C

C++ Implementation

C# Implementation

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:


Please enter your comment!
Please enter your name here

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