Merge Sort Implementation in C++

For a Programmer sorting is an easy task after writing the code for couple of pages. But there are many other sorting algorithms. 

The question which is not being properly answered is which sorting algorithm you should choose. 

This is the most frustrating situation where we feel bad about us. The best sorting algorithm depends only on the scenario in which you are intended to use. 

Let us speak about the Merge sort.

1. Merge sort uses the divide and conquer approach.
2. Entirely the merge sort is an easy algorithm (Depends on the way you think).
3. You cannot master merge sort until you think what is happening.
4. It has a good worst case performance (0(N logN)).
5. It uses an additional space to accomplish the goal.
6. The implementation is mainly based on the recursion.
7.  You can get real performance benefit when comparing to bubble,selection sort.

That's enough for the quick intro. If you would like you know more do a research on yourself.

The algorithm goes like this:

• Take the array and divide it until you get single element.
• Each array will yield two sub-arrays. Each sub-array will give two and goes on..
• Now at the end you will get only single elements.
• All the single elements are again combined in the same way while ensuring the elements are in the proper order.
• Finally you will get the sorted array as a present. 

Don't panic looking at the algorithm, i will ensure good amount of comments n my code.


Just look at the image to get good view of what is happening.

Just looking at the image is not sufficient. Get your hands dirty by working with pen and paper.
Don't get surprised about the failure. Do it again and again until you get success.

The code goes here...

	#include <iostream>
	#include <ctime>//To calculate the running time of program with iostream redirected to files.
	using namespace std;
	/*merge function is a helper function that combine the two splitted array while sorting them together.*/
	void merge(unsigned int array[], int start, int mid, int end)
	{
	//unsigned int array[] contains all the elments while the,
	//index start,mid,end is used to split them into two halves.
	unsigned int *tempArray = new unsigned int[end - start + 1]; //A temporary array to store sorted list
	int p = start, q = mid + 1, k = 0; //Control variables to controll three arrays
	//p - first half of array, q- second half of array, k - temp array;
	for (int i = start; i <= end ; i++) //This loop runs for number of elements from start to end
	{
	if (p > mid) //Case if first half is completed add the second half array to the sorted list.
	{
	tempArray[k++] = array[q++];
	}
	else if (q > end) //Case if second half is completed add the first half to the sorted list.
	{
	tempArray[k++] = array[p++];
	}
	else if (array[p] < array[q]) //Compare for smaller element and put them in temp array;
	{
	tempArray[k++] = array[q++];
	}
	else
	{
	tempArray[k++] = array[p++];
	}
	}
	for (int i = 0; i < k; i++)
	{
	/*This loop will replace the original array with sorted elements in temp array.
	The changes made will be persistant throughout the program. Also the arrays
	are passed as call by reference.*/
	array[start++] = tempArray[i];
	}
	delete[] tempArray; //Deallocate the tempArray to avoid memory leak;
	}
	/*The module for merge sort to be called in the program*/
	void mergeSort(unsigned int data[], int startIndex, int stopIndex)
	{
	/*data[] contains the list */
	if (startIndex < stopIndex) //Base case to end recurssion !important to acheive finite recurssion.
	{
	int midIndex = (startIndex + stopIndex) / 2; //calculating the mid point;
	mergeSort(data, startIndex, midIndex); //Call merge function with left half;
	mergeSort(data, midIndex + 1, stopIndex); //Call merge function with right half;
	merge(data, startIndex, midIndex, stopIndex); //Again combine the array;
	}
	}
	/*Driver module for the merge sort*/
	int main()
	{
	double start_s=clock();
	// the code you wish to time goes here
	int noOfTestCases;
	cin>>noOfTestCases; //nooftestcases specifies the no of list to be sorted.
	int *noOfElements = new int[noOfTestCases]; //To store the number of elements in each list.
	unsigned int **numArray = new unsigned int*[noOfTestCases]; //The 2-D dynamic array to store the list.
	for(int i = 0; i < noOfTestCases ; ++i) //Start of input phase.
	{
	cin>>noOfElements[i];
	numArray[i] = new unsigned int[noOfElements[i]]; //Allocating memeory for no of elements in particularr list.
	for(int j = 0 ; j < noOfElements[i]; ++j) //To get input for each elements in list.
	cin>>numArray[i][j];
	}
	//Input job done;
	//Sorting phase starts;
	for(int j = 0; j < noOfTestCases; ++j) //For iterating through each array(test case).
	{
	mergeSort(numArray[j],0,noOfElements[j]-1); //calling Merge sort function with each list.
	for(int k = 0; k < noOfElements[j]; ++k) //For printing the sorted array
	cout<<numArray[j][k]<<' ';
	cout<<endl;
	delete[] numArray[j]; //Deallocate the space of each list.
	}
	delete[] numArray; //Deallocate the space allocated for storing each list.
	delete[] noOfElements;
	double stop_s=clock();
	cout << "time: " << (stop_s-start_s)/double(CLOCKS_PER_SEC) << endl;
	return 0;
	}

view raw Merge_sort.cpp hosted with ❤ by GitHub

Try to code on your own instead of doing a copy paste. Also remember the mantra for success.

CREDIT: HackerEarth.com(Code monk) for the stuff and the image.