Merge sort in C

Merge sort in C C++

We assume each element of the list/array as a separated list. Each single element is sorted by default so we merge down pair of elements using the merging two sorted arrays method. We continue sorting and merging the sub arrays till we obtain the complete sorted array.

Explanation

We will sort [20 10 30 50 60 90 5 7 2] array using merge sort algorithm.

Assume each element of the array as a different list and then recursively sort each of the list and merge them together.

C program for Merge sort iteratively

#include<stdio.h>
#include<stdlib.h>


void merge(int A[], int l, int mid, int h){
    int B[100],i,j,k;
    i = l;
    j = mid+1;
    k = i;
    while(i<=mid && j<=h)
    {
        if(A[i]<A[j])
        {
            B[k++] = A[i++];
        }
        else{
            B[k++] = A[j++];
        }
    }
    for(;i<=mid;i++)
    {
        B[k++] = A[i];
    }
    for(;j<=h;j++)
    {
        B[k++] = A[j];
    }
    for(int i=l;i<=h;i++)
    {
        A[i] = B[i];
    }
}

void IMergeSort(int A[], int n)
{
    int p,l,h,mid,i;
    for(p=2;p<=n;p=p*2)
    {
        for(i=0;i+p-1<n;i=i+p)
        {
            l=i;
            h=i+p-1;
            mid=(l+h)/2;
            merge(A,l,mid,h);
        }
    }
    if(p/2<n)
    {
        merge(A,0,p/2-1,n-1);
    }
}



int main()
{
    int A[10] = {1,5,2,1,6,3,6,2,5,10};
    int i;
    IMergeSort(A,10);
    for(i=0;i<10;i++)
    {
        printf("%d ",A[i]);
    }
    return 0;
}

C program for recursive merge sort

void RMergeSort(int A[], int l, int h)
{
    int mid;
    if(l<h)
    {
        mid = (l+h)/2;
        RMergeSort(A,l,mid);
        RMergeSort(A,mid+1,h);
        merge(A,l,mid,h);

    }
}

Other sorting algorithms

Count sort in C/C++

Merge sort in C/C++

Quick Sort in C/C++

Selection sort in C/C++

Insertion Sort in C/C++

Bubble Sort in C/C++

Criteria for sorting analysis