Merge Sort C


The complexity of merge sort:

The time complexity of merge sort has been discussed in this link.


Code for merge sort:

#include<stdio.h>
void Merge(int a[], int left, int mid, int right, int n)
{
    int leftSize = mid - left + 1, rightSize = right - mid;
    int i, j, k, leftArray[leftSize], rightArray[rightSize];
    for(i=0;i<leftSize;i++)
        leftArray[i] = a[left+i];
    for(i=0;i<rightSize;i++)
        rightArray[i] = a[mid+1+i];
    i = j = 0;
    k = left;
    while(i < leftSize && j < rightSize)
    {
        if(leftArray[i] < rightArray[j])
        {
            a[k++] = leftArray[i];
            i++;
        }
        else
        {
            a[k++] = rightArray[j];
            j++;
        }
    }
    while(i < leftSize)
    {
        a[k++] = leftArray[i];
        i++;
    }
    while(j < rightSize)
    {
        a[k++] = rightArray[j];
        j++;
    }
}
void MergeSort(int a[], int left, int right, int n)
{
    int mid, i;
    if(left < right)
    {
        mid = (left + right) / 2;
        MergeSort(a, left, mid, n);
        MergeSort(a, mid+1, right, n);
        /*Uncomment the comment lines to see what is happening inside the merge sorting process*/
        /*printf("Merging: ");
        for(i=left;i<=mid;i++)
            printf("%d ", a[i]);
        printf("and ");
        for(i=mid+1;i<=right;i++)
            printf("%d ", a[i]);
        printf("\n");*/
        Merge(a, left, mid, right, n);
        /*printf("After Merging:\n");
        for(i=left;i<=right;i++)
            printf("%d ", a[i]);
        printf("\n");*/
    }
}
int main()
{
    int i, n, numbers[100];
    scanf("%d", &n);
    for(i=0;i<n;i++)
        scanf("%d", &numbers[i]);
    MergeSort(numbers, 0, n-1, n);
    printf("Sorted Output:\n");
    for(i=0;i<n;i++)
        printf("%d ", numbers[i]);
    printf("\n");
    return 0;
}
/*
Sample Input:
10 /*Number of integers*/
12 33 44 55 555 66 77 88 99 100

Sample Output:
Sorted Output:
12 33 44 55 66 77 88 99 100 555

*/

Post a Comment

Previous Post Next Post