Merge Sort is a stable algorithm which usually works recursively. The Merge Sort algorithm is based on the principle of divide and conquer. It divides the problem into smaller parts and then try to conquer (solve) them individually.
Let’s suppose we have an array arr which we want to sort in an ascending order by using the Merge Sort algorithm.
2
8
5
3
9
4
1
7
We will continue to divide the array into half until we are only left with individual elemnets.
2
8
5
3
9
4
1
7
2
8
5
3
9
4
1
7
2
8
5
3
9
4
1
7
Now we have successfully divided the whole array into individual parts. Next we will examine the individual items by comparing them with each other and merging them into temporary arrays.
Step 1
Comparing
2
and
8
Is 2 < 8 ?
Yes. Hence, the array will be,
2
8
Step 2
Comparing
5
and
3
Is 5 < 3 ?
No. Hence, the numbers will be swapped and the array will be,
3
5
Step 3
Comparing
9
and
4
Is 9 < 4 ?
No. Hence, the numbers will be swapped and the array will be,
4
9
Step 4
Comparing
1
and
7
Is 1 < 7 ?
Ye. Hence, the array will be,
1
7
The temporary arrays are sorted and are as following,
2
8
3
5
4
9
1
7
Now again we have to compare temporary arrays with each other and sort and merge them in an ascending order.
Step 1
Comparing
2
8
and
3
5
Is 2 < 8 < 3 < 5 ?
The sorted (in an ascending order) temporary array is as following,
2
3
5
8
Step 2
Comparing
4
9
and
1
7
Is 4 < 9 < 1 < 7 ?
The sorted (in an ascending order) temporary array is as following,
1
4
7
9
The temporary arrays are sorted and are as following,
2
3
5
8
1
4
7
9
Next, we have to again compare the temporary arrays with each other and sort and merge them in an ascending order.
Step 1
Comparing
2
3
5
8
and
1
4
7
9
Is 2 < 3 < 5 < 8 < 1 < 4 < 7 < 9 ?
The sorted (in an ascending order) array is as following,
1
2
3
4
5
7
8
9
Finally, the array is sorted in an ascending order.
To sum up, first the array is divided into individual elements. Then the individual elements are compared, sorted and recombnined into one array. In other words, once the elements are divided, we will make our way back by sorting and merging them into a single array.
Time Complexity of Merge Sort
The run-time complexity of Merge Sort algorithm is 0(n log n). It runs in quasilinear time along with quicksort and heapsort.
