Merge Sort in C
In this article we will discuss the Merge Sort Algorithm. Just like Quick Sort it also follows Divide and Conquer technique. This article will be helpful to students for their academic purpose as well as technical interviews. In interviews sorting algorithms are widely asked so it is important to discuss the topic.
Merge Sort divides the array into two equal halves. Merge sort keeps dividing the list into equal halves until it cannot be further divided. Then we compare the pair of one element list into two element list by sorting them. The sorted two element pair is merge into four element list this way merging continues until we get the sorted list.
To proceed with the working process of Merge Sort we should know does divide and conquer technique means?
Divide and Conquer
Divide and Conquer is a technique in which it recursively solves subproblems; each subproblems must be smaller than the original problem. A divide and conquer algorithm has three parts:
Divide up the problem into a lot smaller pieces of the same problem
Conquer the sub problems by recursively solving them. Solve the sub problem as base case
Combine the solutions of the sub problems to solve the original problem
Working of Merge Sort Algorithm
Now let' see the working of Merge Sort Algorithm.
To understand the working let us take an unsorted array(unsorted array means the data present in the array is in jumbled order that is neither in ascending order nor descending)and start sorting it using Merge Sort Algorithm.
Lets start by taking the array elements.
According to merge sort first divide the given array into two equal halves. Merge sort keeps dividing the list into equal halves until it cannot be further divided.
As there are six elements in the given array .So it is divides into two arrays of size 3.
Let's divide it
Now we have to divide these two array into two halves. As there are of size 3. So divide these into new array like the below given figure.
Now we have to divide and make them a single element.
Now we have to combine in the same manner in which they were divided like the opposite
While combining we have to compare the elements and sort them into another array in sorted order.
As our first element is a single present so no need to compare, we have to move to the other two elements and compare them
Since 45 and 35 are not in order. So Sort it. 35 will come first followed by 45
Now 5 is a single element present so no need to compare it.
Let's check 55 and 17 , they are not in correct order. so we need to sort it.
Therefore 17 will be followed by 55
Hence our arrays are completely sorted and they are in correct order
Let's merge it
Again we have to merge the arrays by comparing the elements and putting them in correct order.
In fig 4, 10 is a single element so no need to compare , we will check 35 and 45 they are in correct order. similarly the other array 5 is single present so need to check we will compare 17 and 55 they are also in correct position
Let's merge it
Finally we will merge the two arrays by sorting them in correct order.
Smallest element will come first followed by greater elements, just like the below figure
This way our array will be sorted and it will merge into a single array. Hence sorting is done by using merge sort
Hence our array is sorted. So full process of sorting using Merge sort is represented in the below figure.
Just have a look
As we have learned the working of Merge Sort Lets proceed towards the Pseudo Code.
Pseudo Code Of Merge Sort
We are moving towards the Algorithm of Merge Sort.
Algorithm of Merge Sort
Merge Sort Program in C
Time Complexity
Now let's see the Time complexity of Merge Sort in Best case, worst case, Average case. We will also be learning about space complexity.
Best Case: In Merge Sort best case occur when the array is already sorted.
Worst Case: Worst Case occurs when we have to sort the array elements in ascending order, but its elements are in descending order.
Average Case: Average Case of Merge Sort occurs when the element are in jumbled order i.e. neither in ascending nor in descending order.
Space Complexity
Advantage of Merge Sort
Merge Sort is very well suited for larger datasets
Merge Sort is stable in nature and it arrange the data in proper order.
Disadvantage of Merge Sort
Merge Sort Algorithm uses extra space in sorting.
Even if the array is sorted merge sort goes throughout the process
When to use Merge Sort
Merge Sort is used when very large of amount of files are needed to sort
Merge Sort can be used with linked list in without taking up any more space.
So far our Merge Sort article comes to an end but before ending we just conclude what are the things that we have learned today.
To conclude, it can be said that
Merge Sort uses divide and conquer technique and has time complexity of O (nlogn)
Merge Sort is very well suited for larger datasets
Merge Sort time complexity i.e. of order O(nlogn) which is better than most of the sorting algorithms.
Main Banner Image Credit: timesofindia.indiatimes.com
