Draggable Slider Tabs | CodingNepal

Merge Sort In C

Merge Sort in C

MergeSort Source Code in C (Helpful Explanation)

Explore the C source code for MergeSort with a helpful explanation. In our previous tutorial, we delved into the concepts and pseudocodes of the merge sort algorithm. Today, we focus solely on the programming aspect. Before diving in, remember to divide the array until subarrays reach size 1. Then, utilize the merge function to combine these subarrays into larger, sorted ones. The end result? A fully sorted array. I’ll illustrate this process using an example from our previous lecture. If you haven’t grasped these concepts, I recommend reviewing the previous lecture before delving into the coding part.

MergeSort in C

Figure: Point-1

MergeSort in C

Figure: Point-2

Now, let’s shift our focus to the programming part after discussing what we did yesterday. I’ve provided the source code below; follow it as we continue.

To comprehend the code snippet:

1. Before delving into the merge and mergeSort functions, let’s incorporate the printArray section into our existing programs. This copying step will save time. A print function is beneficial for observing the array’s contents before and after sorting. The snippet for the printArray function is also included.

				
					void printArray(int* A, int n){
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
}
				
			

Code Snippet 1: Making the printArray function

2. Next, make an array of elements by copying from our previous lecture. Define an integer variable to store the array size.

Creating the merge function:

3. This is the merge function, merging two sorted arrays into a bigger sorted one. Keep the pseudo code for better understanding. Make a void function called merge, taking the array and integer indices low, mid, and high as parameters. Use integer variables i, j, and k to iterate through array A and an auxiliary array B. Create array B with a larger size, say 100, initializing i with low, j with mid+1, and k with low. Here, i marks the current element of the first subarray of array A, and j marks the first element of the second subarray. K is the iterator for array B to insert the smaller of elements at indices i and j.

Run a while loop until either i or j or both reach the threshold of their corresponding subarray. Inside the loop, check if the element at index i is smaller than the one at index j. If it is, insert the element at index i in index k of array B (B[k] = A[i]) and increment both i and k by 1. Otherwise, insert the element at index j in index k of array B (B[k] = A[j]) and increment both j and k by 1.

The loop ends when either i or j or both reach their corresponding subarray’s end. Now, run two separate while loops to insert the remaining elements, if left, in both subarrays. This finishes filling all elements in sorted order in array B. The last step is to copy the sorted array back to array A, and we are done.

				
					void merge(int A[], int mid, int low, int high)
{
    int i, j, k, B[100];
    i = low;
    j = mid + 1;
    k = low;

    while (i <= mid && j <= high)
    {
        if (A[i] < A[j])
        {
            B[k] = A[i];
            i++;
            k++;
        }
        else
        {
            B[k] = A[j];
            j++;
            k++;
        }
    }
    while (i <= mid)
    {
        B[k] = A[i];
        k++;
        i++;
    }
    while (j <= high)
    {
        B[k] = A[j];
        k++;
        j++;
    }
    for (int i = low; i <= high; i++)
    {
        A[i] = B[i];
    }
}

				
			

Snippet 2: Making the merge function

To create the mergeSort function:

4. Make a simple function called mergeSort, and give it the array’s address and the index values low and high. Initially, set low to 0, and high to length – 1.

Recursively call this function only if low is less than high, meaning there are at least two elements in the subarray; otherwise, stop.

Create an integer mid for the mid-element index. Recursively call mergeSort twice, changing the parameters to (low, mid-1) for the left subarray and (mid+1, high) for the right subarray. This sorts the left and right halves. Merge them back into the array by calling the merge function with the array and index variables low, mid, and high. This process returns a sorted array.

				
					void mergeSort(int A[], int low, int high){
    int mid; 
    if(low<high){
        mid = (low + high) /2;
        mergeSort(A, low, mid);
        mergeSort(A, mid+1, high);
        merge(A, mid, low, high);
    }
}

				
			

Code Snippet 3: Creating the mergeSort function

Here is the whole source code:

				
					#include <stdio.h>

void printArray(int *A, int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
}

void merge(int A[], int mid, int low, int high)
{
    int i, j, k, B[100];
    i = low;
    j = mid + 1;
    k = low;

    while (i <= mid && j <= high)
    {
        if (A[i] < A[j])
        {
            B[k] = A[i];
            i++;
            k++;
        }
        else
        {
            B[k] = A[j];
            j++;
            k++;
        }
    }
    while (i <= mid)
    {
        B[k] = A[i];
        k++;
        i++;
    }
    while (j <= high)
    {
        B[k] = A[j];
        k++;
        j++;
    }
    for (int i = low; i <= high; i++)
    {
        A[i] = B[i];
    }
    
}

void mergeSort(int A[], int low, int high){
    int mid; 
    if(low<high){
        mid = (low + high) /2;
        mergeSort(A, low, mid);
        mergeSort(A, mid+1, high);
        merge(A, mid, low, high);
    }
}

int main()
{
    // int A[] = {9, 14, 4, 8, 7, 5, 6};
    int A[] = {9, 1, 4, 14, 4, 15, 6};
    int n = 7;
    printArray(A, n);
    mergeSort(A, 0, 6);
    printArray(A, n);
    return 0;
}

				
			

Code Snippet 4: Program to implement the Merge Sort Algorithm

Now, let’s see if our functions are working correctly. Think about an array A with a size of 7.

				
					    int A[] = {9, 1, 4, 14, 4, 15, 6};
    int n = 7;
    printArray(A, n);
    mergeSort(A, 0, 6);
    printArray(A, n);

				
			

Code Snippet 5: Using the mergeSort function

The result we got was:

				
					9 1 4 14 4 15 6
1 4 4 6 9 14 15 
PS D:\MyData\Business\code playground\Ds & Algo with Notes\Code>

				
			

Figure 1 shows the result of the program we just did.

Now, try sorting your arrays using the merge sort method. Rewatch any part if needed and make sure you get it all.

That covers the merge sort algorithm. The MergeSort function is good, but understanding how merging works is key. Practice these algorithms on your own. We’ve covered 5 sorting algorithms in total. Test your memory and apply them to sort your arrays.

Thanks for your support. I hope you liked the tutorial. Share it with your friends if you found it helpful

Merge Sort in C

Leave a Comment

Your email address will not be published. Required fields are marked *