Divide And Conquer Approach

                Do you like Burgers? Let consider the process of eating Burger. A person can eat the burger in one bite or More than one bite. You must be thinking of the person who can eat the whole burger in just one bite, But generally, we eat the burger in more than one bite. A number of bites takes to eat the whole burger depends upon burger size as well as the size of each bite. We eat burger bite by bite because we cannot chew or put the whole burger in the mouth. Another reason for taking Many bites is because it is easier to handle small bite than the whole burger.

                In Education, we cannot teach/learn whole life oriented things in one single part. So we divide life aspects into fields of study. Again we cannot handle any particular field as single. So further we divide the field into subjects. Each subject has many books to learn it. Same as Book into chapters and Chapters into sections and section into figures, tables, paragraphs etc. Further Paragraph divides into sentences and sentence into words and word into letters. That’s why every child first learns alphabets of any language.In Big Company, CEO/Owner cannot handle all the work of company by hand. So Company has different departments, Each department has the general manager and Each General manager handle group of managers of the particular department. Each manager handles the group of workers.

                Again, back to the former example of Eating burger. Now Consider Burger as Big Computational Problem and Mouth as Processor of Computer. The processor can handle a small part of actual Big Computational problem easily. This type of algorithm which first divide the problem into the small problem until the problem becomes small enough to handle easily called Divide and Conquer Algorithm.

Merge Sort 

Merging Of Solutions

                Sorting of the array can be done with divide and conquer approach. For sorting of the array, first, we break array into smaller arrays and solve smaller array or break again into smaller arrays and solve them. Here the question is what is the minimum size of the array to be sorted. If we break the main array until all subarrays have one element. We already have sorted array because the array has only one element and In any order ascending or descending one element has its correct position. But the only division of array doesn’t give us the correct output of actual array to be sorted. For having the correct Sorted array of the input array, We have to merge these smaller sorted arrays into the big sorted array until we achieve correct array as output. This algorithm involving the merging of the smaller solution to achieve the Sorting solution, so it is called MERGESORT.

                As Merge sort involves breaking and merging of an array. It contains two functions to perform Merge Sort: merge-sort & merge. MergeSort algorithm demonstrate in C/C++ language for Sorting Integers.

	/*
	Merge_Sort using Two Function
	1. merge(array,left,mid,right)
	which merge two sorted array into One Sorted Array
	2. Merge_Sort(array,left,right)
	which sort the array
	*/
	/*
	Merge Function of Merge_Sort
	Time Complexity : O(n)
	Space Complexity : O(n)
	*/
	void merge(int data_array[],int left,int mid,int right)
	{
	//determine number of elements in subarrays
	int element_left=mid-left+1;
	int element_right=right-mid;
	//create temporary array with proper size
	int tmp_left[element_left],tmp_right[element_right];
	//copy data into temporary left array
	for(int i=0;i<element_left;i++)
	tmp_left[i]=data_array[left+i];
	//copy data into temporary right array
	for(int i=0;i<element_right;i++)
	tmp_right[i]=data_array[mid+i+1];
	//Now merge the two temporary array into data_array[left...right]
	//assign Initial Index of arrays
	int IndexOfLeft=0,IndexOfRight=0,IndexOfMergeArray=left;
	//merge arrays
	while(IndexOfLeft < element_left && IndexOfRight < element_right)
	{
	if(tmp_left[IndexOfLeft] <= tmp_right[IndexOfRight])
	{
	data_array[IndexOfMergeArray]=tmp_left[IndexOfLeft];
	IndexOfLeft++;
	IndexOfMergeArray++;
	}
	else
	{
	data_array[IndexOfMergeArray]=tmp_right[IndexOfRight];
	IndexOfRight++;
	IndexOfMergeArray++;
	}
	}
	//Now put remaining Elements of left OR right array as it is in Merge array
	while(IndexOfLeft<element_left)
	{
	data_array[IndexOfMergeArray]=tmp_left[IndexOfLeft];
	IndexOfLeft++;
	IndexOfMergeArray++;
	}
	while(IndexOfRight<element_right)
	{
	data_array[IndexOfMergeArray]=tmp_right[IndexOfRight];
	IndexOfRight++;
	IndexOfMergeArray++;
	}
	}
	/*
	Merge_Sort Function for Perform sorting on Integer Array
	Time Complexity : O( n log n )
	Space Complexity : O(n) //when array used
	: O( log n ) //when linked list used
	*/
	//call function as merge(array_to_be_sorted,first_position,Last_position)
	void Merge_Sort(int data_array[],int left,int right)
	{
	if(left < right)
	{
	//divide array from middle element
	int mid= left + (right-left)/2;
	//sort first half of array
	Merge_Sort(data_array,left,mid);
	//sort second half of array
	Merge_Sort(data_array,mid+1,right);
	//now merge the sorted result
	merge(data_array,left,mid,right);
	}
	}

view raw Merge_Sort.cpp hosted with ❤ by GitHub