Merge Sort in CPP

Whats is Merge Sort ?

Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sub-list consists of a single element and merging those sub-lists in a manner that results into a sorted list.

What is Divide And Conquer ?

Divide and conquer is cutting an problem in a recursive manner by continually dividing the problem into smaller and smaller parts before solving the smaller parts and then combining the results.

Who Invented Merge Sort ?

Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Working

An Unsorted Array In Array[Size]. The task is to rearrange the array elements in ascending order.
Merge Sort is known as a Divide and Conquer algorithm: given a task, divide it into parts; then solve the parts individually.

 There are two parts to the Merge Sort algorithm.

1. Divide the list Array into two separate lists
2. Merge the new lists together in order

First let’s look at Divide. The algorithm is simple: divide Array Size into left and right halves. This process is recursive, and does not stop until only one element remains in the list. A single-element list is already sorted.

Merge Section : it merges two lists (left and right) into a single list newarray[Size] in ascending order. Merge also makes a claim: lists left and right are already sorted. Since left and right are already sorted in ascending order, the two lists can be merged by repeatedly removing the next lowest value in both lists and shift newarray[size] to Array[size]. This operation requires only a single comparison per value added to the result list, until one list is exhausted.

Worst complexity: n*log(n)
Average complexity: n*log(n)
Best complexity: n*log(n)
Space complexity: n

Program

//Merge Sort
#include<iostream.h>
#include<conio.h>
//Display function
void display(int array[],int size){
	cout<<" ";
	for(int i=0;i<=size;i++){
		cout<<array[i];
		(size==i)? cout<<".": cout<<",";
	}
}
//Swap Function
void swap(int array[],int left,int right){
	//Interchange Two Element in Array
	int temp = array[left];
	array[left] = array[right];
	array[right] = temp;
}
//Merge Two Array
void merge_array(int array[],int low,int mid,int high){
	 //stores the starting position of both parts in temporary variables.
	int h=low;
	int l=low;
	int m=mid+1;
	int new_array[20]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}; // Blank Array	
	while((h<=mid)&&(m<=high))
		 //checks which part has smaller element.
		if(array[h]<=array[m]){  
			new_array[l]=array[h];
			h++;
		}else{ 						
			new_array[l]=array[m];
			m++;
		}
		l++;
	}
	if(h>mid){ 
		//checks if first part comes to an end or not .
		for(int k=m;k<=high;k++){
			new_array[l]=array[k];
			l++;
		}
	}else{
		//checks if second part comes to an end or not
		for(int k=h;k<=mid;k++){
			new_array[l]=array[k];
			l++;
		}
	}
	/* New array elements shift into array in sorted manner including both parts.*/
	for(int k=low;k<=high;k++){
		array[k] = new_array[k];
	}
}
//Merge Sort
void merge_sort(int array[],int low,int high){
	int mid;
	if(low<high){
		mid=(low+high)/2;
		merge_sort(array,low,mid);	//Split Array LOW <----> MID
		merge_sort(array,mid+1,high); 	//Split Array MID+1 <----> HIGH
		merge_array(array,low,mid,high); // Merge Array in Sorted Form
	}
}
//Main Function
void main(){
	clrscr();	//Clear Screen
	int array[11]={40,60,50,70,10,30,80,90,55,20}; // Array
	int size=9;	//Size
	int low=0;
	cout<<"\n ------ Merge Sort ------ ";
	cout<<"\n Before Sorting\n";
	display(array,size); 	//Display Before Sort
	merge_sort(array,low,size);	//Merge Sorting
	cout<<"\n After Sorting\n";
	display(array,size);		//Display After Sorting
	getch();
}

Output