my simple merge sort

I know that merge sort is one of the best sorting algorithms. But i don’t think that it improves the speed in case of c programming. Stack Effect of recursive functions will slow down the program. I think other languages don’t have this effect.


#include <stdio.h>
#define MAX_LENGTH 100000
int mergedivide(int a[], int low, int high);
int mergeconquer(int a[], int low, int mid, int high);
int main()
{
    int a[MAX_LENGTH],i;
    int n;
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    mergedivide(a,0,n-1);
    for (i = 0; i < n; ++i)
        printf("%d ", a[i]);
return 0;
}
int mergeconquer(int a[], int low, int mid, int high)
{
    int b[MAX_LENGTH];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high)
    {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    while (i <= mid)
        b[k++] = a[i++];
    while (j <= high)
        b[k++] = a[j++];
    k--;
    while (k >= 0)
    {
        a[low + k] = b[k];
        k--;
    }
return 0;
}
int mergedivide(int a[], int low, int high)
{
    int m;
    if (low < high)
    {
        m = (high + low)/2;
        mergedivide(a, low, m);
        mergedivide(a, m + 1, high);
        mergeconquer(a, low, m, high);
    }
return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s