Skip to content

Instantly share code, notes, and snippets.

@hardikpatil

hardikpatil/MergeSort_C.C

Forked from mycodeschool/MergeSort_C.C
Created October 19, 2021 18:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save hardikpatil/b9b27469e1a515c99b759d4c76c68a5b to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save hardikpatil/b9b27469e1a515c99b759d4c76c68a5b to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @mycodeschool mycodeschool revised this gist Feb 19, 2015. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions MergeSort_C.C
    View file
    Original file line number Diff line number Diff line change
    @@ -40,6 +40,8 @@ void MergeSort(int *A,int n) {
    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() {
  2. @mycodeschool mycodeschool created this gist Mar 21, 2014.
    63 changes: 63 additions & 0 deletions MergeSort_C.C
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,63 @@
    /* 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.
    }

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