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;
}

// c++code!

#include
using namespace std;

void mergearrays(int A, int Left,int leftcount, int* Right, int rightcount){

int i,ii,jj;
i=0;ii=0;jj=0;
while(i< leftcount+rightcount){

    if(ii == leftcount) A[i++] = Right[jj++];
    else if(jj == rightcount) A[i++] = Left[ii++];
    else{
        A[i++] = (Right[jj] > Left[ii]) ? Left[ii++]: Right[jj++];
    }
}

}
void mergeSort(int* A, int n){
int mid = n/2;
if(n<2)return;

int* Left= new int[mid];
int* Right= new int[n-mid];

for(int i=0;i<mid;i++)Left[i] = A[i];
for(int i=mid;i<n;i++)Right[i-mid] = A[i];

mergeSort(Left, mid );
mergeSort(Right, n-mid);
mergearrays(A, Left, mid, Right, n-mid);


delete(Left);
delete(Right);
}

int main() {
cout << "Hello World!\n";
int A[]={1,3,4,24,6,7};

int sizel= sizeof(A)/sizeof(A[0]);
mergeSort(A, sizel);
for( int p=0;p<sizel;p++) cout<< A[p]<< endl;

}

Java Code

public class MergeSort {

public static void main(String args[]) {
	int[] a = {100,9,7,4,3,1,11,89,65,43,05,54,21,0,};
	a=ms(a);
	for(int x : a) {
		System.out.print(x+" ");
	}		
}
private static int[] ms(int[] a) {
	int n = a.length; 
	if(n<2) {
		return a;
	}
	else {
	int mid = n/2;

	int[] l = new int[mid];
	int[] r = new int[n-mid];
	for(int i=0;i<mid;i++) {
		l[i]=a[i];
	}
	for(int i=mid;i<n;i++) {
		r[i-mid]=a[i];
	}
	ms(l);
	ms(r);
	merge(l,r,a);
	return a;
	}
	
}
private static void merge(int[] l, int[] r, int[] a) {		
int nl = l.length;
int nr = r.length;
int i =0,j=0,k=0;

while(i<nl && j<nr) {
	if(l[i]<=r[j]) {
		a[k]=l[i];
		i++;
	}
	else {
		a[k]=r[j];
		j++;
	}
	k++;
}
while(i<nl) {
	a[k]=l[i];
	k++;i++;
}
while(j<nr) {
	a[k]=r[j];
	k++;j++;
}		
}

}

Java Code!

public class Test { 
    
    public static void main(String[] args) {
    int[] arr = {6,2,3,1,9,10,15,13,12,17};
    Test.sort(arr);
    for (int i : arr){
        System.out.print(i+ " ");
    }

}
    public static void Merge(int[] left, int[] right, int[] arr){
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length){
            if (left[i] < right[j]){
                arr[k] = left[i];
                i++;
            }
            else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }
        while (i < left.length){
            arr[k] = left[i];
            k++; i++;
        }
        while (j < right.length){
            arr[k] = right[j];
            k++; j++;
        }

    }
    public static void sort(int[] arr){
            int n = arr.length;
            if(n < 2) return;
            int mid = n/2;
            int[] left = Arrays.copyOfRange(arr,0, mid);
            int[] right = Arrays.copyOfRange(arr, mid, n);
            sort(left);
            sort(right);
            Merge(left, right, arr);

    }

}

Thank you so much, sir.

Thanks alot sir, best explanation on internet.

Python implementation, did variables with much wordings for a simpler follow-along,

def mergeSort(array):
	arrayLength = len(array)
	if arrayLength<2:
		return
    #cmpute array mid-point
	mid = arrayLength//2

    # create two lists/array and initialize with default values
	leftArray= list(range(mid))
	rightArray= list(range(arrayLength-mid))
	
    # populate the two arrays with values from original array/list
	for idx in range(mid):
		leftArray[idx] = array[idx]
	for idx in range(mid, arrayLength):
		rightArray[idx-mid] = array[idx]
    
    # call a mergeSort method recursively until the base case of len <2 is reached 
    # means one element is remaining in a given list
	mergeSort(leftArray)
	mergeSort(rightArray)

    #then start merging picking left and right array from call stack
	merge(leftArray,rightArray,array)

    # meged array
	return array
		

def merge(leftArray,rightArray,array):
	leftArrayLength = len(leftArray)
	rightArrayLength = len(rightArray)
	
	leftIdx=rightIdx=arrayIdx=0
	
    # loop until the len of either array
	while(leftIdx < leftArrayLength and rightIdx < rightArrayLength):
		if leftArray[leftIdx] <= rightArray[rightIdx]:
			array[arrayIdx] = leftArray[leftIdx]
			leftIdx +=1
		else:
			array[arrayIdx] = rightArray[rightIdx]
			rightIdx +=1
		arrayIdx +=1
		
    # case when right array is exhausted before the left one
	while leftIdx < leftArrayLength:
		array[arrayIdx] = leftArray[leftIdx]
		leftIdx +=1
		arrayIdx +=1
	
    # case when left array is exhausted before the left one
	while rightIdx < rightArrayLength:
		array[arrayIdx] = rightArray[rightIdx]
		rightIdx +=1
		arrayIdx +=1


# tests
testArray =[6,2,3,1,9,10,15,13,12,17]
expected = [1, 2, 3, 6, 9, 10, 12, 13, 15, 17]

assert mergeSort(testArray) == expected

Merge sort in java

`class mergeSortAlgorithms{

public void merge(int arr[], int start , int mid , int end){

//find the size of right and left halves
int n1 = mid - start +1;
int n2 = end - mid;

//make the temporary array equal to right and left halve
int left[] = new int[n1];
int right[] =  new int[n2];

//fill the right and left halves
for(int i=0;i<n1;i++){
  left[i] = arr[i+start];
}
for(int j=0;j<n2;j++){
    right[j] = arr[mid+1+j];
}
//intialize variable
int i = 0 ,j=0, k = start;

//sort the array
while(i<n1 && j <n2){

  if(left[i] < right[j]){
    arr[k] = left[i];
    i++;
  }
  else{
    arr[k] = right[j];
    j++;
  }
  k++;
}
//copying the reamaining value of right and left halves
while(i<n1){
  arr[k] =left[i];
  i++;
  k++;
}
while(j<n2){
  arr[k] = right[j];
  j++;
  k++;
}

}
public void mergeSort(int arr[], int start ,int end){
//check if start greater than end
if(start < end){
int mid = (start+end)/2;

  //divide into two halves recursively
  mergeSort(arr,start,mid);
  mergeSort(arr,mid+1,end);


  //merge into two halves
  merge(arr,start,mid,end);
}

}
public static void main(String[] args) {
//random array
int arr[] = {25,20,4,24};

//object of same class
mergeSortAlgorithms array = new mergeSortAlgorithms();
//call the mergesort function
array.mergeSort(arr,0,arr.length-1);
//display sorted array
for (int i=0;i<arr.length ;i++ ) {
    System.out.println(arr[i]);
}

}
}

`

To compile and run online same program : click on this link :
https://debuggingsolution.blogspot.com/2021/09/mergesort.html

To see code :
https://debuggingsolution.blogspot.com/2021/09/mergesort.html

i did the array split in 1 loop

for(i = 0;i<mid;i++){
	 L[i] = A[i];
	 R[i] = A[mid+i];
}
if(n%2)R[i] = A[mid+i];

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