Merge Sort: What is Merge sort and Its complexity

Hi, this is Shubham Mishra, today we will be going to discuss on a topic which deals with the sorting of an array. In my algorithm series, this is the first post but previously I also have written other posts such as Python game develop using Pygames and Data structure and data structure types.

The today's topic is Merge sort algorithm. In the series of the algorithm, we will discuss all the possible kind of algorithms and also its complexity with the condition for the use of such algorithms. Let's discuss Merge sort algorithm, its time complexity. Merge sort is a very efficient sorting algorithm with the near-optimal number of comparisons. It is best described using a Recursive algorithm approach. The working of merge sorting algorithm is to splitting and merging of two sorted lists into one sorted list. The recursive algorithm used for merge sort comes under the category of divide and conquer technique. An array of n elements is split around its centre which leads to two small arrays. In this way, the two sub-arrays are further divided into half until a condition match and then all the small subarrays are sort independently and merged to produce the sorted array. Bored, don't worry we have below diagrammatic representation for the above text.

Merge Sort Algorithm

In the above diagram, we do have an Initial array as [ 34, 5, 9, 14, 64, 8] and we get our sorted array at the last step. It is self-explanatory that how things are working in the above diagram. Now let's jump into the coding.

	#include<stdio.h>
	#include<conio.h>
	void merge_sorting_function( int[], int, int);
	void merge_with_sorting_function( int[], int, int, int);
	void main(){
	//Here I have considered my own array u can replace it with actual code for accepting
	// it from user
	int array = [34, 5, 9, 14, 64, 8];
	int n = sizeof(array);
	int i;
	//Call merge_sorting_function
	merge_sorting_function(array, 0, n-1);
	//Now print the sorted array
	for(i=0; i<n; i++)
	printf("%d", array[i]);
	getch();
	}
	void merge_sorting_function(int array[], int i, int j){
	int k;
	if (i<j) //Condition checked for further division of array into subarray or not
	{
	k = (i+j) / 2; // Find out the centre point for division
	merge_sorting_function( array, i, k); //Apply merge sort steps for left sub array
	merge_sorting_function( array, k+1, j); //Apply merge sort steps for right sub array
	merge_with_sorting_function( array, i, k, j); //This is imp call for actual merging subarrays
	}
	}
	void merge_with_sorting_function( int array[], int l, int m, int u){
	//The l,m,u are nothing but the indexes used to get the subarrays
	//The left subarray is from l to m, the right sub array is from m+1 to u
	int temp[100]; //This temp array is used for merging
	int i,j,k;
	i = l;
	j = m+1;
	k = 0;
	while( i <= m && j <= u){ //merging two subarrays
	if( array[i] < array[j]){ //Checking which entity is bigger
	temp[k] = array[i];
	i++;
	k++;
	}
	else{
	temp[k] = array[j];
	j++;
	k++;
	}
	}
	//Below two while loops are used to copy remaning part of subarrays into temp
	/*Suppos two subarrays are of size 3 and 5, Once all the element of any one subarray
	is transfered to temp array then remaining elements of another array is copied to
	the temp array
	*/
	while( i <= m){
	temp[k] = array[i];
	i++;
	k++;
	}
	while( j <= u){
	temp[k] = array[j];
	j++;
	k++;
	}
	//Now copy the sorted temp array back into the original array
	for( i = l, j = 0; i <= u; i++, j++)
	array[i] = temp[j];
	}

view raw Merge Sort Code : Shubham Mishra hosted with ❤ by GitHub

Done with the code part.

Now let's discuss the complexity of merge sort algorithm. The merge sort algorithm's main computation power required for 'merge_with_sorting_function' this function, when the subarrays are merged and get sorted. Its time complexity is O(N log N), where N is the total number of elements in the array.

While considering its complexity one important thing need to consider is the memory required by this algorithm, but that is a one more arrays as in our case it was 'temp[]' which is not harmful so I would like to conclude that Merge Sort algorithm is an Efficient algorithm.

Thanks for scrolling down, In my upcoming posts I would like to discuss more and more algorithms and will also differentiate them from others.

Thank You !!!

See my all posts Shubham Mishra

Visit Radix Sort algorithm

Ok great, we are done with this post,  

Now if you like my way of talk, lets explore more blogs written by me and my inner knowledge,

Get to know answers for common search on Google : A blog for posts which can help you for daily life problems, such as where to get free images, Topic suggestion for the blog.

Computer Science algorithms and other knowledge share : A blog for posts such as best search algorithm, Top interview questions for diffrent technologies, knowledge share for some frameworks or programming languages for the interview or in general terms.

My ideas to solve real world problems : A blog where me shared and presented my ideas to solve a real world problems, this will be interesting for me.

Future of computer science technology discussed : A blog where me discussed about the future of computer science and new technologies which will change our way for looking to solve problems.

Ruby on Rails Web development Blog : As the name suggest, it is the blog for sharing few knowledge about RoR web development framework.

Liked my blogs, wanna to connect:

LinkedIn  |  GitHub  |  HackerEarth  |  ResearchGate  |  Twitter  |  Facebook  |  StackOverflow

Thanks for reading this post, Have a good day :)