Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
/* 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;
}
@locdoremon

This comment has been minimized.

Copy link

@locdoremon locdoremon commented Mar 23, 2014

Awesome! Thanks, I've watched your video on youtube, Your teaching way is very easy to understand. You're the best teacher I've ever learned,sir. :)

@ObjSal

This comment has been minimized.

Copy link

@ObjSal ObjSal commented Apr 11, 2014

This is a nice very clear implementation, but the implementation from this other site runs a little bit faster:
http://vinayakgarg.wordpress.com/2012/11/08/merge-sort-program-in-c/

But in this other implementation instead of having
int b[10000];
I do:
int b = malloc(sizeof(int)(high - low + 1));
...
free(b);

@macfij

This comment has been minimized.

Copy link

@macfij macfij commented Oct 8, 2014

You should add free(L); free(R); at the end of Merge() function.

@rajmiglani

This comment has been minimized.

Copy link

@rajmiglani rajmiglani commented Nov 11, 2014

best teacher to learn from..yeah rightly said locdoremon

@wegi77

This comment has been minimized.

Copy link

@wegi77 wegi77 commented Feb 2, 2015

Hi Guys,
how can:
L = (int_)malloc(mid_sizeof(int));
R = (int_)malloc((n- mid)_sizeof(int));

part be replaced in the same implementation in C#?

Thanks in advance...

edit:
mid = n / 2;
L = new int[mid];
R = new int[n - mid];
would be enough?

@raosumanth

This comment has been minimized.

Copy link

@raosumanth raosumanth commented Feb 17, 2015

The above code would have lot of memory leaks, checked the memory leaks through valgrind tool.
Need to add free (L) and free (R) towards the end of the method mergeSort().

@ht89

This comment has been minimized.

Copy link

@ht89 ht89 commented Jul 19, 2015

Thank you so much for sharing. Your code & comments are so easy to understand.

@veerendra2

This comment has been minimized.

Copy link

@veerendra2 veerendra2 commented Aug 24, 2015

Thanks for the nice explanation.
At line numbers 20 and 21 in the above code. you mentioned
while(i < leftCount) A[k++] = L[i++];
while(j < rightCount) A[k++] = R[j++];
Instead of while loop, can we use "IF"? or is there any specific reason for "WHILE"?. Because, after exiting the main while loop(line no. 16), there should be 1 element left either in left array or right array.

For example, if the condition in mail while loop fails, the control goes to 2nd or 3 rd while loop. In those loops, we are not checking any conditions, simply putting the remaining elements in main array.Then why we are using WHILE loop? I hope you understood what I'm saying or may be I misunderstood the algorithm. Thanks!

@UziahAkmalBhatti

This comment has been minimized.

Copy link

@UziahAkmalBhatti UziahAkmalBhatti commented Dec 6, 2015

I have tried the same logic for linked list but as far as the liked list is of size 2 it works fine but starts to problem beyond that please guide me.

@vivekab

This comment has been minimized.

Copy link

@vivekab vivekab commented Feb 17, 2016

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?

@spyreto

This comment has been minimized.

Copy link

@spyreto spyreto commented Mar 6, 2016

Thank very much! Very helpful explanation!

@kanersan

This comment has been minimized.

Copy link

@kanersan kanersan commented Apr 28, 2016

Thank you so much. Works perfectly!

@igniteram

This comment has been minimized.

Copy link

@igniteram igniteram commented Jun 25, 2016

👍

@code0monkey1

This comment has been minimized.

Copy link

@code0monkey1 code0monkey1 commented Jun 27, 2016

Pure C++ implementation of Merge_Sort:

#include <iostream>

using namespace std;


void merge(int* ALR, int* L, int left_length, int* R, int right_length) {
    int l = 0;
    int r = 0;
    for (int i = 0; i < left_length + right_length;) {

        if (l == left_length)ALR[i++] = R[r++];
        else if (r == right_length)ALR[i++] = L[l++];
        else ALR[i++] = (R[r] > L[l]) ? L[l++] : R[r++];

    }
}

void merge_sort(int* ALR, int length) {

    if (length == 1)return;

    int mid = length / 2;

    int* L = new int[mid];
    int* R = new int[length - mid];

    int k = 0;

    for (size_t i = 0; k < mid; i++)L[i] = ALR[k++];
    for (size_t i = 0; k < length; i++)R[i] = ALR[k++];

    merge_sort(L, mid);
    merge_sort(R, length - mid);

    merge(ALR, L, mid, R, length - mid);
    delete(L);
    delete(R);
}
int main() {

    int A[] = { 1,3,4,7,2,8,5,6,9 };

    int size = sizeof(A) / sizeof(A[0]);

    merge_sort(A, size);

    for (size_t i = 0; i < size; i++)cout<<A[i]<<" ";



}
@fsociety123

This comment has been minimized.

Copy link

@fsociety123 fsociety123 commented Aug 5, 2016

//MERGE SORT

include <stdio.h>

include <stdlib.h>

int n,i,j,k;

void display(int a[20],int n)
{
for(i=0;i<n;i++)
{printf("\t%d",a[i]);}
printf("\n");
}

void merge(int l[20],int r[20],int a[20],int lc,int rc)
{
i=0;
j=0;
k=0;
while(j<lc && k<rc)
{
if(l[j]<r[k])
{
a[i]=l[j];
i++;
j++;
}
else
{
a[i]=r[k];
i++;
k++;
}
}
while(j<lc)
{
a[i]=l[j];
j++;
i++;
}
while(k<rc)
{
a[i]=r[k];
i++;
k++;
}
}

void merge_sort(int a[20],int n)
{

int mid;
if(n<2)
    return;
mid=n/2;

int l[mid],r[n-mid];
for(i=0;i<mid;i++)
    l[i]=a[i];
for(i=mid;i<n;i++)
    r[i-mid]=a[i];

merge_sort(l,mid);
merge_sort(r,n-mid);
merge(l,r,a,mid,n-mid);

}
void main()
{
int a[20],mid;
printf("\nEnter the number of elements:\n");
scanf("%d",&n);
for(i=0;i<n;i++)
a[i]=rand()%100;
printf("\nUnsorted array:\n");
display(a,n);
merge_sort(a,n);
printf("\nSorted array:\n");
display(a,n);
}

@EdisonHsien

This comment has been minimized.

Copy link

@EdisonHsien EdisonHsien commented Aug 22, 2016

Now, it feels better to understand Merge Sort.

@raviavanigadda

This comment has been minimized.

Copy link

@raviavanigadda raviavanigadda commented Aug 28, 2016

Thanks Easy to understand and implement..!

@sanhnguyennt

This comment has been minimized.

Copy link

@sanhnguyennt sanhnguyennt commented Sep 3, 2016

Sirs, What are the purposes of the two lines at the end of merge():
while(i < leftCount) A[k++] = L[i++];
while(j < rightCount) A[k++] = R[j++];

I thought L and R have already been merged into A with:

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

This comment has been minimized.

Copy link

@NuclearMachine NuclearMachine commented Sep 6, 2016

Thanks for the concise and simple yet detailed explanation!

@MinaGhali

This comment has been minimized.

Copy link

@MinaGhali MinaGhali commented Sep 14, 2016

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

@Masum-Osman

This comment has been minimized.

Copy link

@Masum-Osman Masum-Osman commented Oct 29, 2016

Clean and easy...

@saurin2

This comment has been minimized.

Copy link

@saurin2 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

This comment has been minimized.

Copy link

@tahi12 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

This comment has been minimized.

Copy link

@harshraijiwala harshraijiwala commented Apr 15, 2017

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

This comment has been minimized.

Copy link

@samar88doc samar88doc commented Jun 5, 2017

best one!!!!!!!

@Nayananga

This comment has been minimized.

Copy link

@Nayananga Nayananga commented Jan 28, 2018

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

}

@mmeisson

This comment has been minimized.

Copy link

@mmeisson mmeisson 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

This comment has been minimized.

Copy link

@ktrishala 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

This comment has been minimized.

Copy link

@Shivan11 Shivan11 commented May 16, 2018

@vivekab Perfect solution. Clean code and less variables.

@Kailash23

This comment has been minimized.

Copy link

@Kailash23 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

This comment has been minimized.

Copy link

@axiom2018 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.

@Atum-Ra

This comment has been minimized.

Copy link

@Atum-Ra Atum-Ra commented May 18, 2019

Why use dynamic memory ?

@RahulSrivatava

This comment has been minimized.

Copy link

@RahulSrivatava RahulSrivatava commented Dec 9, 2019

Thak u it works perfectly fine!!

@kumarmanish52

This comment has been minimized.

Copy link

@kumarmanish52 kumarmanish52 commented Dec 15, 2019

                **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

This comment has been minimized.

Copy link

@RahulSrivatava RahulSrivatava commented Dec 16, 2019

@tridibsamanta

This comment has been minimized.

Copy link

@tridibsamanta tridibsamanta commented May 7, 2020

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

This comment has been minimized.

Copy link

@tridibsamanta 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

This comment has been minimized.

Copy link

@DonutsDevil DonutsDevil commented Aug 14, 2020

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

This comment has been minimized.

Copy link

@JESSE-max1 JESSE-max1 commented Aug 18, 2020

why are we taking arrays as pointers?

@Mayur8991

This comment has been minimized.

Copy link

@Mayur8991 Mayur8991 commented Sep 27, 2020

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

This comment has been minimized.

Copy link

@Swagnika Swagnika commented Feb 12, 2021

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

This comment has been minimized.

Copy link

@Jasmine-liang 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

This comment has been minimized.

Copy link

@ImranWahidCoder ImranWahidCoder commented Feb 25, 2021

Thank you so much, sir.

@derrick-gopher

This comment has been minimized.

Copy link

@derrick-gopher derrick-gopher 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment