Instantly share code, notes, and snippets.

# mycodeschool/MergeSort_C.C Last active Dec 16, 2019

 /* Merge sort in C */ #include #include // 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

### 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 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; I do: int b = malloc(sizeof(int)(high - low + 1)); ... free(b);

### macfij commented Oct 8, 2014

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

### rajmiglani commented Nov 11, 2014

 best teacher to learn from..yeah rightly said locdoremon

### 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 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 commented Jul 19, 2015

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

### 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 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 commented Feb 17, 2016

 void merge(int a[], int low, int mid, int high) { int b; 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 commented Mar 6, 2016

 Thank very much! Very helpful explanation!

### kanersan commented Apr 28, 2016

 Thank you so much. Works perfectly!

 👍

### code0monkey1 commented Jun 27, 2016 • edited

 Pure C++ implementation of Merge_Sort: ``````#include 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); merge_sort(A, size); for (size_t i = 0; i < size; i++)cout<

//MERGE SORT

# include <stdlib.h>

int n,i,j,k;

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

void merge(int l,int r,int a,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,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,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 commented Aug 22, 2016

 Now, it feels better to understand Merge Sort.

### ravigamer95 commented Aug 28, 2016

 Thanks Easy to understand and implement..!

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

### NuclearMachine commented Sep 6, 2016

 Thanks for the concise and simple yet detailed explanation!

### MinaGhali commented Sep 14, 2016

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

### Masum-Osman commented Oct 29, 2016

 Clean and easy...

### 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 commented Mar 30, 2017 • edited

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

### 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 commented Jun 5, 2017

 best one!!!!!!!

### 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 commented Mar 17, 2018 • edited

 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 commented Apr 11, 2018 • edited

 Where am I going wrong? #include #include void Merge(int *left,int lcnt,int *right,int rcnt,int *arr) { int i=0,j=0,k=0; while(i

### Shivan11 commented May 16, 2018

 @vivekab Perfect solution. Clean code and less variables.

## 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);`
` MergeSort(arr, n);`
` PrintArray(arr, n);`
` return 0;`
`}`

### axiom2018 commented Apr 12, 2019 • edited

 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.

### 3BlueIBrown commented May 18, 2019

 Why use dynamic memory ?

### RahulSrivatava commented Dec 9, 2019

 Thak u it works perfectly fine!!

### kumarmanish52 commented Dec 15, 2019

 `````` **merge sort program in C by Studyinight Programmer** `````` https://codegcloudonline.blogspot.com/2019/12/merge-sort.html #include int merge(int *,int ,int ,int); void mergesort(int *,int ,int); main() { int n,a,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

### RahulSrivatava commented Dec 16, 2019

 A zj … On Mon, 16 Dec 2019, 02:18 kumarmanish52 ***@***.*** wrote: **merge sort program in C by Studyinight Programmer** https://codegcloudonline.blogspot.com/2019/12/merge-sort.html #include int merge(int *,int ,int ,int); void mergesort(int *,int ,int); main() { int n,a,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, or unsubscribe .