Skip to content

Instantly share code, notes, and snippets.

@mycodeschool
Last active July 2, 2024 12:39
Show Gist options
  • Save mycodeschool/9678029 to your computer and use it in GitHub Desktop.
Save mycodeschool/9678029 to your computer and use it in GitHub Desktop.
/* 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;
}
@NuclearMachine
Copy link

Thanks for the concise and simple yet detailed explanation!

@MinaGhali
Copy link

Why didn't you create the subarrays as automatic variables in stack and used memory allocation instead?

@Masum-Osman
Copy link

Clean and easy...

@saurin2
Copy link

saurin2 commented Jan 16, 2017

When i tried to ran this code for 2MB or more of elements it failed, any suggestion on that?

@tahi12
Copy link

tahi12 commented Mar 30, 2017

i tried to do the same prog but i am having errors i am not having clear idea about dynamic array. can anyone please guide me it crash after taking input.
#include "stdafx.h"
#include
using namespace std;

void Merge_Sort(int h, int m, int U[], int V[], int S[])
{

int i = 1, j = 1, k = 1;
while ((i <= h) && (j <= m)){
	if (U[i] < V[j])
	{
		S[k] = U[i];
		i++;
	}
	else
	{
		S[k] = V[j];
	}
	k++;
}
if (i > h)
{
	for (int l = j; l < m; l++)
	{
		S[k] = V[l];
	}

}
else
{
	for (int l = j; l < m; l++)
	{
		S[k] = U[l];
	}
}

}
void Merge_Sort(int n, int S[])
{
int const c = 1000;
if (n < 2)
return;
int h, m;
h = n / 2;
m = n - h;

int * U = new int[c];
int * V = new int[c];
for (int i = 0; i < h; i++)
{
	U[i] = S[i];
}
for (int j = h; j < n; j++)
{
	V[j] = S[j];
}

Merge_Sort(h, U);
Merge_Sort(m, V);
Merge_Sort(h, m, U, V, S);

}

int main()
{
int const m = 1000;
int * arr = new int[m];
int n;
cin >> n;

for (int i = 0; i < n; i++)
{
	cin >> arr[i];
}

// delete[] arr;
Merge_Sort(n, arr);

for (int i = 0; i < n; i++)
{
cout<< arr[i]<<endl;
}
system("pasue");

}

@harshraijiwala
Copy link

Does following function create new L and R for every cycle of merge sort that is called in the loop ? or does it overwrites the previous L and R. I know that after merging L and R is made free. But in the initial loop before first merge occurs does it makes new L and R or it just overwrites the previous L and R?
L = (int*)malloc(midsizeof(int));
R = (int
)malloc((n- mid)*sizeof(int));

@samar88doc
Copy link

best one!!!!!!!

@Nayananga
Copy link

/*
I tried to implement this using java,please tell me where i`m wrong because i get wrong sorted array
*/
public class MergeSort1 {
public static void main (String args[]) {
int A [] = {3,5,1,0,6,7,4,2};
sort(A);
for(int i = 0; i < A.length; i++ ){
System.out.print(A[i]+" ");
}

}
public static int [] sort (int A[] ) {
    int n = A.length;
    if (n >2) {
        int mid = n / 2;
        int left [] = new int [mid];        
        int right [] = new int [n - mid]; 
        for(int i = 0; i < mid - 1; i++) {
            left [i] = A [i];
            
        }
        for(int i = mid; i < n - 1; i++) {
            right [i - mid] = A [i];
            
        }
        sort(left);
        sort(right);
        merge(left,right,A);
    }
    
    return A;
}
public static void merge (int L [], int R [], int A []) {
    int nl = L.length;
    int nr = R.length;
    int i = 0;
    int j = 0;
    int 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];
         i++;
         k++; 
    }
     while (j < nr) {
        A[k] = R [j];
         j++;
         k++; 
    }
     
}

}

Copy link

ghost commented Mar 17, 2018

This implementation consume an high amount of memory, nearly (M^2) / 2 ... An in place implementation could be harder to implement, but you could instead do your temporary allocation stuff in Merge instead of in MergeSort

@ktrishala
Copy link

ktrishala commented Apr 11, 2018

Where am I going wrong?

#include<stdio.h>
#include<stdlib.h>
void Merge(int *left,int lcnt,int *right,int rcnt,int *arr)
{
int i=0,j=0,k=0;
while(i<lcnt&&j<rcnt)
{
if(left[i]<=right[j])
{
arr[k]=left[i];
i++;
}
else
{
arr[k]=right[j];
j++;
}
k++;
}
while(i<lcnt)
{
arr[k]=left[i];
i++;
k++;
}
while(j<rcnt)
{
arr[k]=right[j];
j++;
k++;
}

}
void MergeSplit(int *arr, int n)
{
int mid, *left,*right;

if(n<=1)
{
    return;
}
mid=n/2;
left = (int*)malloc(mid*sizeof(int)); 
right= (int*)malloc((n-mid)*sizeof(int)); 
for (int i=0;i<mid;i++)
{
    left[i]=arr[i];
}
for(int j=0;j<n-mid;j++)
{
    right[j]=arr[j];
}
MergeSplit(left,mid);
MergeSplit(right,n-mid);
 
Merge(left,mid,right,n-mid,arr);
free(left);
free(right);

}

void main()
{
int arr[]={5,2,1,7,4};
int n=sizeof(arr)/sizeof(arr[0]);
MergeSplit(arr,n);
for(int i=0;i<5;i++)
{
printf("%d",arr[i]);
}
}

@Shivan11
Copy link

@vivekab Perfect solution. Clean code and less variables.

@Kailash23
Copy link

Kailash23 commented May 27, 2018

C++ version of above code as explained in the video.

#include<iostream>
using namespace std;

void Merge(int left[], int right[], int arr[], int nL, int nR) {

int i = 0;
int j = 0;
int k = 0;

while (i < nL && j < nR) {
if (left[i] < right[j]) {
arr[k] = left[i];
i = i + 1;
} else {
arr[k] = right[j];
j = j + 1;
}
k = k + 1;
}

while (i < nL) {
arr[k] = left[i];
i = i + 1;
k = k + 1;
}

while (j < nR) {
arr[k] = right[j];
j = j + 1;
k = k + 1;
}
}

void MergeSort(int arr[], int n) {
if (n < 2) {
return;
}

int mid = n / 2;
int left[mid];
int right[n - mid];

for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}

for (int i = mid; i < n; i++) {
right[i - mid] = arr[i];
}

MergeSort(left, mid);
MergeSort(right, n - mid);
Merge(left, right, arr, mid, n - mid);
}

void PrintArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
}

int main() {
int arr[] = { 6, 2, 3, 1, 9, 10, 15, 13, 12, 17 };
int n = sizeof(arr) / sizeof(arr[0]);
MergeSort(arr, n);
PrintArray(arr, n);
return 0;
}

@axiom2018
Copy link

axiom2018 commented Apr 12, 2019

This is great, thanks for teaching us in your merge sort video but is it NECESSARY to use dynamic arrays for the algorithm? I've seen implementations that don't require it.

@web3dev6
Copy link

Why use dynamic memory ?

@RahulSrivatava
Copy link

Thak u it works perfectly fine!!

@kumarmanish52
Copy link

                **merge sort program in C by Studyinight Programmer**

https://codegcloudonline.blogspot.com/2019/12/merge-sort.html
#include<stdio.h>
int merge(int *,int ,int ,int);
void mergesort(int *,int ,int);
main()
{
int n,a[40],i,p,r;
printf("Enter total no of element in an array\n");
scanf("%d",&n);
printf("Enter total %d element in an array\n",n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("\nElement Before sorting\n");
for(i=1;i<=n;i++)
printf("%d\t",a[i]);
p=1;
mergesort(a,p,n);
printf("\nElement After sorting\n");
for(i=1;i<=n;i++)
printf("%d\t",a[i]);
}
void mergesort(int *a,int p,int r)
{
int q;
if(p<r)
{
q=(p+r)/2;
mergesort(a,p,q);
mergesort(a,q+1,r);
merge(a,p,q,r);
}
}
int merge(int *a,int p,int q,int r)
{
int n1,n2,l[30],m[30],i,j,k;
n1=q-p+1;
n2=r-q;
for(i=1;i<=n1;i++)
l[i]=a[p+i-1];
for(j=1;j<=n2;j++)
m[j]=a[q+j];
l[n1+1]=1234567897;
m[n2+1]=1234567898;
i=1;j=1;
for(k=p;k<=r;k++)
{
if(l[i]<=m[j])
{
a[k]=l[i];
i=i+1;
}
else
{
a[k]=m[j];
j=j+1;
}
}
return a;
}

@RahulSrivatava
Copy link

RahulSrivatava commented Dec 16, 2019 via email

@tridibsamanta
Copy link

Dynamic memory is used to so that we can de-allocate (free) the left and the right sub-array memory space once the process completes. A good programming practice indeed.

@tridibsamanta
Copy link

tridibsamanta commented May 7, 2020

void merge(int a[], int low, int mid, int high)
{
int b[10000];
int i = low, j = mid + 1, k = low;

while (i <= mid && j <= high) {
    if (a[i] <= a[j])
        b[k++] = a[i++];
    else
        b[k++] = a[j++];
}
while (i <= mid)
    b[k++] = a[i++];

while (j <= high)
    b[k++] = a[j++];

for(i=low;i<=high;i++)
    a[i]=b[i];
}

}

void mergesort(int a[], int low, int high)
{
if (low < high) {
int m = (high + low)/2;
mergesort(a, low, m);
mergesort(a, m + 1, high);
merge(a, low, m, high);
}
}

why are we not implementing this code?

Following issues with the above mentioned method -

  1. What if the array size if more than 10000 ?
  2. There can be lot of empty cells in array 'b[]', and wastage of memory is costly !
  3. What happens to array 'b[]' when the merge() finishes execution for the last time ? After that we don't need the array 'b[]' again, as the elements are in sorted order in array 'a[]', right ? See, we need to free the memory allocated to array 'b[]', which is not done here. :(

@DonutsDevil
Copy link

Java Implementation of the Merge Sort!

public class MergeSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int arr[] = {2,10,7,5,1,3,0,11};
		mergeSort(arr);
		for(int i : arr) {
			System.out.print(i+" ");
		}

	}
	
	
	
	static void mergeSort(int A[]) {
		
		int n = A.length;
		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);
		mergeSort(right);
		merge(left,right,A);
	}
	
	
	// this merges the sorted left and right array into one array;
	static void merge(int left[],int right[], int arr[]){
		
	int l = 0;	
	int r = 0;
	int k = 0;
	
	while(l < left.length && r < right.length) {
		
		if(left[l] <= right[r]) {
			arr[k] = left[l];
			l++;
		}else{
			arr[k] = right[r];
			r++;
			}
		
		k++;
		
		}//end of while
	while(l<left.length) {
		arr[k] = left[l];
		k++;
		l++;
		}
	while(r<right.length) {
		arr[k] = right[r];
		k++;
		r++;
		}
	}

}// end of class

@JESSE-max1
Copy link

why are we taking arrays as pointers?

@Mayur8991
Copy link

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

}

@Swagnika
Copy link

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

}

@Jasmine-liang
Copy link

Jasmine-liang commented Feb 15, 2021

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

    }

}

@ImranWahidCoder
Copy link

Thank you so much, sir.

@d3rrick
Copy link

d3rrick commented Mar 7, 2021

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

@row-star-134
Copy link

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

@asesami
Copy link

asesami commented Nov 30, 2021

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

@darshandodamani
Copy link

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

@AKASH-ALAM
Copy link

thanks

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment