Thread: Natural Mergesort

iMalc wrote that you need 200% more space than the original array, since you need two temporary arrays, that you alternately write to (depending on the condition he explained). When you arrive at the end of your original array, you merge the two temporary arrays according to his criteria and then start again, at the beginning of the input array, until you only write to one temporary array only (in which case the numbers are sorted).

To complete my sorting algorithm collection, I tried implementing the natural mergesort that iMalc suggested, following the exact description he gave in this thread (code is below here). The thing is that this is incredibly slow, 0.87 seconds on an array of size 10k compared to bubbleSort that performed in 0.86 seconds on the same values. A classic mergeSort takes 0.0 seconds (value to small to be visible) for the same values.

I wonder if I have a mistake in my code (I tested it with debugging and it works just as expected) or is that thing really that slow ??

Code:

static void naturalMerge(int **in, int *out, size_t size, int *tmpSize);

void naturalMergeSort(int *array, int size)
{
    int i = 0;
    /* switchArray points alternately to our 2 tmp arrays */
    int switchArray;

    /* two temporary arrays */
    int **tmp;

    /* two index, one for each temporary array */
    int index[2];

    tmp = malloc(2 * sizeof(*tmp));
    tmp[0] = malloc(size * sizeof(**tmp));
    tmp[1] = malloc(size * sizeof(**tmp));

    do
    {
        /* reset everything to the start */
        i = 0;
        switchArray = 0;
        index[0] = 0;
        index[1] = -1;

        /* write the first element of our array into the first tmp array */
        tmp[switchArray][index[switchArray]] = array[i];
        for (i = 1; i < size; i++)
        {
            /* check if we can still build a monotonic sequence */
            if (array[i] >= tmp[switchArray][index[switchArray]])
            {
                tmp[switchArray][++index[switchArray]] = array[i];
            }
            else
            {
                switchArray = (++switchArray)&#37;2;
                tmp[switchArray][++index[switchArray]] = array[i];
            }
        }
        /* merge the two temporary arrays into our original array */
        naturalMerge(tmp, array, size, index);
    } while (index[1] != -1);
    free(tmp[0]);
    free(tmp[1]);
    free(tmp);
}

/**
 * in[0] and in[1] are our two temporary arrays we want to merge
 * out is the original array the two temporary arrays are merged into
 * size is the size of the original array
 * tmpSize is the size of in[0], in[1]
 */

void naturalMerge(int **in, int *out, size_t size, int *tmpSize)
{
    int i, j = 0, k = 0;
    for (i = 0; i < size; i++)
    {
        if (j > tmpSize[0] || k > tmpSize[1])
            break;
        if(in[0][j] < in[1][k])
        {
            out[i] = in[0][j++];
        }
        else
        {
            out[i] = in[1][k++];
        }
    }

    while (j <= tmpSize[0])
        out[i++] = in[0][j++];

    while (k <= tmpSize[1])
        out[i++] = in[1][k++];
}

Originally Posted by KONI

Seriously, I tried to make sense of what you wrote but I just don't understand it. Just split your initial array recursively in half, cutting at the middle.

KONI, you mention about splitting it in half recursively at the middle, and to exploit naturally present bitonic sequences,

So, would it be that i split it recursively like a top-down mergesort, but,
merge(function) it differently?

Originally Posted by wuzzo87

KONI, you mention about splitting it in half recursively at the middle, and to exploit naturally present bitonic sequences,

So, would it be that i split it recursively like a top-down mergesort, but,
merge(function) it differently?

Ignore that post, that was about the classic merge sort that doesn't exploit any natural order. Please refer to the code I posted above and also to the comment iMalc wrote that fixed the O(n*n) into O(n*log n) complexity.

Hey guys, i wanted to the performance in terms of comparisons of this algorithm from http://www.inf.fh-flensburg.de/lang/...e/natmerge.htm
against my other bottom-up mergesort program.
I implemented a static int that's pass from main to the functions.
But the result is always 0.... why?

Here's my translation of C++ to C:

Code:

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

void sort(int array[],int size, int comp);
static bool mergeruns(int a[], int b[], int n, int comp);
void merge(int a[], int b[], int lo, int hi, bool asc, int comp);
void naturalmergesort(int a[], int b[], int n, int comp);


int main(int argc, char **argv)
{
        int array[50];
        int item,j, i=0;
        static int comp=0;

        while(scanf("%d", &item) > 0)
        {
                array[i] = item;
                i++;
        }

        sort(array,i,comp);

        for(j=0; j < i; j++)
                printf("%d ", array[j]);

        printf("\n");
        printf("%d comparisons made\n", comp);

        return 0;
}

void sort(int array[],int size, int comp)
{
        int b[50];
        int n=size;
        naturalmergesort(array, b, n, comp);
}


static bool mergeruns(int a[], int b[], int n, int comp)
{
        int i=0, k=0, x;
        bool asc=true;

        while (i<n)
        {
            k=i;
            do x=a[i++]; while (i<n && x<=a[i]);
            while (i<n && x>=a[i]) x=a[i++];
            merge (a, b, k, i-1, asc, comp);
            asc=!asc;
        }
        return k==0;
}


void merge(int a[], int b[], int lo, int hi, bool asc, int comp)
{
        int l = lo; int r = hi;
        int k=asc ? l : r;
        int c=asc ? 1 : -1;
        int i=lo, j=hi;

        while (i<=j)
        {
            if (a[i]<=a[j])
            {
                b[k]=a[i++];
                comp++;
            }
            else
            {
                b[k]=a[j--];
                comp++;
            }
            k+=c;
        }
}


void naturalmergesort(int a[], int b[], int n, int comp)
{
        while (!mergeruns(a, b, n, comp) & !mergeruns(b, a, n, comp));
}

Hmm...
Ok, I used static thinking that, it'll be initialised to 0 once, in the start of the main func,
then it get passed to the functions, [to sort() then naturalmergesort () then mergeruns() then merge() - where it gets increamented] and since it's static so the value to its final increament should hold where i then print it out once all the sorting is done.
Then i should know how many comparisons were made when merging.

Tht's what i think.....at least

If you want to get a performance reference other than time, you could simply measure the clock() difference between the start and the end of the program and not divide that by CLOCKS_PER_SEC. In that case you will know exactly how many clocks the algorithm needed.

Hi guys,
I actually need to also count the comparisons, but I thank you for the timing suggestion too , of which i will be using and is of great help.

However, what units will the result be for the time difference of clock()? My result is always 0.0000 .... I'm running it on Mandrake 10.1....
It's under >> man clock? ...because they said, clock ticks are miliseconds.

And apart from that, can i get a lil help on pointers again? My comparison pointer keeps on printing 0....

Here's what i did..

Code:

int main(int argc, char **argv)
{
        int array[50];
        int item,j, i=0;
        int *comp = malloc(sizeof(int));
        int comp_result;
        clock_t start, stop;
        double t;

        while(scanf("%d", &item) > 0)
        {
                array[i] = item;
                i++;
        }

        start = clock();

        sort(array,i,comp);

        stop = clock();

        t = (double)(stop-start);

        comp_result = *comp;

        for(j=0; j < i; j++)
                printf("%d ", array[j]);

        printf("\n");
        printf("%d comparisons made\n", comp_result);
        printf("Time taken : %.10lf\n", t);


        return 0;
}

void sort(int array[],int size, int *comp)
{
        int b[50];
        int n=size;
        naturalmergesort(array, b, n, comp);
}


static bool mergeruns(int a[], int b[], int n, int *comp)
{
        int i=0, k=0, x;
        bool asc=true;

        while (i<n)
        {
            k=i;
            do x=a[i++]; while (i<n && x<=a[i]);
            while (i<n && x>=a[i]) x=a[i++];
            merge (a, b, k, i-1, asc, comp);
            asc=!asc;
        }
        return k==0;
}

void merge(int a[], int b[], int lo, int hi, bool asc, int *comp)
{
        int l = lo; int r = hi;
        int k=asc ? l : r;
        int c=asc ? 1 : -1;
        int i=lo, j=hi;
        int comparisons = 0;

        while (i<=j)
        {
            if (a[i]<=a[j])
            {
                b[k]=a[i++];
                comparisons++;
            }
            else
            {
                b[k]=a[j--];
                comparisons++;
            }
            k+=c;
        }
        comp = &comparisons;
}


void naturalmergesort(int a[], int b[], int n, int *comp)
{
        while (!mergeruns(a, b, n, comp) & !mergeruns(b, a, n, comp));
}

Originally Posted by wuzzo87

And apart from that, can i get a lil help on pointers again? My comparison pointer keeps on printing 0....

Someone help me with pointers plz...
it's the last bit of my prog and it's all done. waahhaahaa...