MergeSort_C.C

/* Merge sort in C */
#include<stdio.h>
#include<stdlib.h>

// Function to Merge Arrays L and R into A. 
// lefCount = number of elements in L
// rightCount = number of elements in R. 
void Merge(int *A,int *L,int leftCount,int *R,int rightCount) {
	int i,j,k;

	// i - to mark the index of left aubarray (L)
	// j - to mark the index of right sub-raay (R)
	// k - to mark the index of merged subarray (A)
	i = 0; j = 0; k =0;

	while(i<leftCount && j< rightCount) {
		if(L[i]  < R[j]) A[k++] = L[i++];
		else A[k++] = R[j++];
	}
	while(i < leftCount) A[k++] = L[i++];
	while(j < rightCount) A[k++] = R[j++];
}

// Recursive function to sort an array of integers. 
void MergeSort(int *A,int n) {
	int mid,i, *L, *R;
	if(n < 2) return; // base condition. If the array has less than two element, do nothing. 

	mid = n/2;  // find the mid index. 

	// create left and right subarrays
	// mid elements (from index 0 till mid-1) should be part of left sub-array 
	// and (n-mid) elements (from mid to n-1) will be part of right sub-array
	L = (int*)malloc(mid*sizeof(int)); 
	R = (int*)malloc((n- mid)*sizeof(int)); 
	
	for(i = 0;i<mid;i++) L[i] = A[i]; // creating left subarray
	for(i = mid;i<n;i++) R[i-mid] = A[i]; // creating right subarray

	MergeSort(L,mid);  // sorting the left subarray
	MergeSort(R,n-mid);  // sorting the right subarray
	Merge(A,L,mid,R,n-mid);  // Merging L and R into A as sorted list.
        free(L);
        free(R);
}

int main() {
	/* Code to test the MergeSort function. */
	
	int A[] = {6,2,3,1,9,10,15,13,12,17}; // creating an array of integers. 
	int i,numberOfElements;

	// finding number of elements in array as size of complete array in bytes divided by size of integer in bytes. 
	// This won't work if array is passed to the function because array
	// is always passed by reference through a pointer. So sizeOf function will give size of pointer and not the array.
	// Watch this video to understand this concept - http://www.youtube.com/watch?v=CpjVucvAc3g  
	numberOfElements = sizeof(A)/sizeof(A[0]); 

	// Calling merge sort to sort the array. 
	MergeSort(A,numberOfElements);

	//printing all elements in the array once its sorted.
	for(i = 0;i < numberOfElements;i++) printf("%d ",A[i]);
	return 0;
}

I had implemented the Merge sort class for the divide and conquer method. The main method is written different.

public class divideandconquer {
//Implement the sorting algorithm Merge Sort, which you will have to use in the
//algorithm for solving Closest-Points. (25%)
//**************
//Not implemented the sort() function. Instead of that
//Merge sort class
class Merge{
private static int k;
static void mergeSort(ArrayList A, int start, int end) {
//check condition if start greater than end
if(start < end) {
//using a formula
int mid = (start + (end-1)) / 2;
//Now we divide into two valves for multiple times
mergeSort(A, start, mid);
mergeSort(A, mid+1, end);
//merge into two valves
merge(A, start, mid, end);
}
}
public static void merge(ArrayList A, int startpoint, int midpoint, int endpoint ) {
//Calculate the size of left and right halves
int lefthalve = midpoint - startpoint + 1 ;
int righthvalve = endpoint - midpoint ;
//create a temporary sub-arrays and assigned to calculated left halves
int [] left = new int[lefthalve];
//create a temporary sub-arrays and assigned to calculated right halves
int [] right = new int [righthvalve];
//We fill our sorted right sub-arrays into temporaries
for (int leftIndex = 0; leftIndex < lefthalve; ++leftIndex) {
left[leftIndex] = A.get(startpoint+leftIndex);
}
//We fill our sorted left sub-arrays into temporaries
for (int rightIndex = 0; rightIndex < righthvalve; ++rightIndex) {
right[rightIndex] = A.get(midpoint + 1 + rightIndex);
}
//Initialize the variables, iterators containing current index of temp sub-arrays
int leftIndex = 0; int rightIndex = 0; int k=startpoint;
// copying from leftArray and rightArray back into array
//for (int i = start; i < end + 1; i++) {
while(leftIndex < lefthalve && rightIndex < righthvalve) {
if(left[leftIndex]<right[rightIndex]) {
A.set(k, left[leftIndex]);
leftIndex++;
}
else {
A.set(k, right[rightIndex]);
rightIndex++;
}
k++;
}
// if all the elements have been copied from rightArray, copy the rest of leftArray
while (leftIndex < lefthalve) {
A.set(k, left[leftIndex]);
leftIndex++;
k++;
}
// if all the elements have been copied from leftArray, copy the rest of rightArray
while (rightIndex < righthvalve) {
A.set(k, right[rightIndex]);
rightIndex++;
k++;
}
}
//applying getters and setters of defined k value
public static int getK() {
return k;
}
public static void setK(int k) {
Merge.k = k;
}
}
}

thanks