C Language Practice: Sorting - Merge Sort

Merge Sort

What is merge sort?

Hooray! We have another way of sorting - merge sort! This type of sorting is pretty fast in my opinion. What we want to do in merge sort(there are also different ways people can understand this. This is only my opinion. You can search for other opinions if you like) is that we start by cutting the list. We cut the list in halves, then we cut the halves into halves, and we cut those halves into halves again and again until there's only one element in the cut list(list: why do I have to get cut?). Then, we do as the name says, we start to merge them together. We combine two elements into a sorted list, and we combine two lists with two elements into a sorted list with four elements(that may not be the case because the number of elements in the list may not be even) and we repeat until we combined the whole list! This may not sound so fast, but you can go to these visualized diagrams of sorting methods and look at the other diagrams(except Shell Sort, which is even faster than merge sort in the diagram) and then look at merge sort. It's surprisingly faster than the others(this will show the most if you pull the animation speed slider to the fastest speed)!

PS: Sshhh, don't tell others! It's a secret! If you slide the speed slider a little bit to the left, and you click on the sorting methods and watch the animation, you can understand them! But don't forget to randomize the array though!(wait, why did I made it italic? Oops!)

By the way, there is a surprise at the end!

Help! How can I code merge sort?

Let's start getting the steps into action!

But before we start though, we have to make sure what method of coding we will use! In this case, I will use recursion(by the way, if you do not know what is recursion, come here to recursion!), which is easier to write but slower. If you want your code to be faster, be sure to search for other opinions!

• Step 1: We have to define a $merge$ function! In it, we'll code like:

Important! We'll need four parameters in this function: $array,l(left),m(middle)$ and $r(right)$!

• • Step 1.1 in $merge$: We'll need three variables that will help us with our loops: $i,j$, and $k$!
  • Step 1.2 in $merge$: We'll let n1 be $m-l+1$, which is the length of the left side of our $array$ and n2 be $r-m$, which is the length of the right side of our $array$!
  • Step 1.3 in $merge$: We'll create two lists, $L[n1](left)$ and $R[n2](right)$ and use two for loops with $i$ and $j$ to copy the data from the left and right side of the array into the two lists!
  • Step 1.4 in $merge$: Be sure to initialize $l,j$ and $k$!
  • Step 1.5 in $merge$: Ok, one while loop with $i<n1\&\&j<n2$ will keep us running until one list is done sorting. Inside, we'll have:
    • Step 1.5.1 in $merge$'s $whileloop$: An $if$ that tells us if the $i$th element in $L$ is smaller than or equal to the $j$th element in $R$ and synchronize that in the $array$. Also, we'll add one to $i$ because that will get us to the next element in $L$!
    • Step 1.5.2 in $merge$'s $whileloop$: An $else$ will tell us that the $i$th element in $L$ is greater than the $j$th element in $R$ and synchronize it in our $array$. Also, we'll add one to $j$ because that will get us to the next element in $R$!
  • Step 1.6 in $merge$: Another while with $i<n1$ will keep putting the sorted array $L$ into $array$.
  • Step 1.7 in $merge$: One last while with $j<n2$ will keep putting the sorted array $R$ into $array$.

And oof, we're done!

• Step 2: Merge sort starts! We'll have three parameters: $array[],l,r$. We'll say if $l<r$, then we'll define $m$ to be the middle and use recursion by using two merge sorts with $array,l,m$ and $array,m+1,r$, which will cut the list in halves. Then, we'll add in the if another line, $merge$ with parameters $array,l,m,r$.

And we're done!

• Step 3: Get the main function and boom! We're done!

Here's the code:

#include <stdio.h>

int merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1=m-l+1;
    int n2=r-m;
    int L[n1], R[n2];
    for(i=0;i<n1;i++)
        L[i]=arr[i+l];
    for(j=0;j<n2;j++)
        R[j]=arr[j+m+1];
    i=0;
    j=0;
    k=l;
    while(i<n1&&j<n2)
    {
        if(L[i]<=R[j])
        {
            arr[k]=L[i];
            i++;
        }
        else
        {
            arr[k]=R[j];
            j++;
        }
        k++;
    }
    while(i<n1)
    {
        arr[k]=L[i];
        i++;
        k++;
    }
    while(j<n2)
    {
        arr[k]=R[j];
        j++;
        k++;
    }
    return arr;
}

int mergeSort(int arr[], int l, int r)
{
    if(l<r)
    {
        int m=l+(r-l)/2;
        mergeSort(arr, l, m);
        mergeSort(arr, m+1, r);
        merge(arr, l, m, r);
    }
    return arr;
}

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

int get_arr(int arr[], int t)
{
    printf("num list here please\n");
    for(int i=0; i<t; i++)
        scanf("%d", &arr[i]);
    return arr;
}

int main(void)
{
    int t;
    printf("how many nums do you want to enter\n");
    scanf("%d", &t);
    int arr[t];
    get_arr(arr, t);
    printf("sorted arr\n");
    mergeSort(arr, 0, t-1);
    printf_arr(arr, t);
    return 0;
}