Dynamic Memory Allocation In MERGE SORT

[xavier666]

I just received the MERGE SORT code from my friend, here it is

void sort_merge     (int *array, int low, int high)
{
    int mid;

    if (low < high)
    {
        mid = (low + high) / 2;
        sort_merge  (array, low, mid);
        sort_merge  (array, mid + 1, high);
        array_merge (array, low, high, mid);
    }
}

void array_merge    (int *array, int low, int high, int mid)
{
    int i = low;
    int j = mid + 1;
    int k = low;
    int array_temp[50];

    while (i <= mid && j <= high)
    {
        if (array[i] < array[j])
        {
            array_temp[k++] = array[i++];
        }
        else
        {
            array_temp[k++] = array[j++];
        }
    }

    while (i <= mid)
    {
        array_temp[k++] = array[i++];
    }

    while (j <= high)
    {
        array_temp[k++] = array[j++];
    }

    for (i = low; i < k; i++)
    {
        array[i] = array_temp[i];
    }
}

It's running okay, however, it has a problem. You'll see that in array_merge, it has declared array_temp[50] and
hence, it is static. If size of array is small, this program becomes inefficient and if
size of array is large, this won't work. So i made a modification, that is,
printed the values of low, high & k

void array_merge    (int *array, int low, int high, int mid)
{
    int i = low;
    int j = mid + 1;
    int k = low;
    int array_temp[50];

    while (i <= mid && j <= high)
    {
        if (array[i] < array[j])
        {
            array_temp[k++] = array[i++];
        }
        else
        {
            array_temp[k++] = array[j++];
        }
    }

    while (i <= mid)
    {
        array_temp[k++] = array[i++];
    }

    while (j <= high)
    {
        array_temp[k++] = array[j++];
    }

    printf("\n\n\t\tLENGTH OF ARRAY - %d\tLOW - %d\tHIGH - %d", k, low, high);  //  THE CHANGED PORTION

    for (i = low; i < k; i++)
    {
        array[i] = array_temp[i];
    }
}

Here is the output

SIZE OF ARRAY = 10

INPUT - 10,1,9,2,8,3,7,4,6,5

LENGTH OF ARRAY - 2     LOW - 0 HIGH - 1

LENGTH OF ARRAY - 3     LOW - 0 HIGH - 2

LENGTH OF ARRAY - 5     LOW - 3 HIGH - 4

LENGTH OF ARRAY - 6     LOW - 3 HIGH - 5

LENGTH OF ARRAY - 6     LOW - 0 HIGH - 5

LENGTH OF ARRAY - 8     LOW - 6 HIGH - 7

LENGTH OF ARRAY - 9     LOW - 6 HIGH - 8

LENGTH OF ARRAY - 11    LOW - 9 HIGH - 10

LENGTH OF ARRAY - 11    LOW - 6 HIGH - 10

LENGTH OF ARRAY - 11    LOW - 0 HIGH - 10

By printing the value of 'k', i know what the maximum value of the size of array_temp can be.
By observation, i saw that 'k = high + 1' for each time it is called

So i again modified my program, by making the memory allocation of 'array_temp' dynamic

void array_merge    (int *array, int low, int high, int mid)
{
    int i = low;
    int j = mid + 1;
    int k = low;
    int *array_temp = (int *)calloc(high + 1, sizeof(int));     //  DYNAMIC ALLOCATION

    while (i <= mid && j <= high)
    {
        if (array[i] < array[j])
        {
            array_temp[k++] = array[i++];
        }
        else
        {
            array_temp[k++] = array[j++];
        }
    }

    while (i <= mid)
    {
        array_temp[k++] = array[i++];
    }

    while (j <= high)
    {
        array_temp[k++] = array[j++];
    }

    for (i = low; i < k; i++)
    {
        array[i] = array_temp[i];
    }
    
    free(array_temp);
}

But the problem with this is that when i sort and print the array, the array elements gets deleted
I just can't understand what the problem is. Some help would be greatly appreciated

By the way, this problem gets solved if i write int *array_temp = (int *)malloc(sizeof(array)); But I think there is a better solution

Thanks, in advance!

[abhimanipal]

Can you tell me where did you write the print function ? I wrote the print function in the main after the sort function was called and I was able to print the array elements just fine.

[xavier666]

Actually, i wrote the print command as a function.

void array_display  (int *array, int size_of_array)
{
    int i;
    for (i = 0; i < size_of_array; i++)
    {
        printf("\n\t\t\t%d.\t%d", (i + 1), array[i]);
    }
}

The whole program is in switch case so it actually does not matter where i wrote it

Here is the menu of my program

=========================================
|          SORTING TECHNIQUES           |
=========================================

Establish The Size Of Array           [1]

Enter The Elements Into The Array     [2]

Use Sorting Method : Insertion Sort   [3]

Use Sorting Method : Quick Sort       [4]

Use Sorting Method : Merge Sort       [5]

Use Sorting Method : Shell Sort       [6]

Display The Array                     [7]

Exit                                  [0]

        Enter Choice :

And I've written the respective commands as functions.

Here is another bizarre output of my program

SIZE OF ARRAY - 5

INPUTS - 5,4,3,2,1

LENGTH OF ARRAY - 2     LOW - 0 HIGH - 1

LENGTH OF ARRAY - 3     LOW - 0 HIGH - 2

LENGTH OF ARRAY - 5     LOW - 3 HIGH - 4

LENGTH OF ARRAY - 6     LOW - 3 HIGH - 5

LENGTH OF ARRAY - 6     LOW - 0 HIGH - 5

AFTER SORTING - 3,0,0,0,0

Thanks for your effort though!

[abhimanipal]

Does this problem persist across all the sorting algorithms or just for merge sort ?

[xavier666]

Only for merge sort. The rest of the algorithms do not need a temporary array.
By the way, Happy Holi!

[abhimanipal]

Happy Holi to you also

[Adak]

Only for merge sort. The rest of the algorithms do not need a temporary array.
By the way, Happy Holi!

Radix sort will require an auxiliary array, as well.

What I've done for my AllSorts program, is have the second array made equal to the size of the original array. It is not inefficient, that way, and only limits the size of the total array, at a very large size.

There is a version of merge sort that doesn't require any second array, but it's performance is not as good.

You should not be repeatedly allocating memory - that is a substantial slow down to a sorting program.

I am looking for C code, pseudo code, or a detailed description of the "Library Sort", and haven't been able to find it. If you find it, would you post it up, or let me know?

Have you tried optimizing your Quick sort with Insertion sort, when the size of the sub arrays is about 20- 50 elements? It's a big speed up.

Thanks.

[xavier666]

Radix sort will require an auxiliary array, as well.

I have not used radix sort in my program

What I've done for my AllSorts program, is have the second array made equal to the size of the original array.

But what is the size of the original array? Have you taken the size from user or used # define . Using a macro is cheap but if the size of the temporary array is to be of the same size as the original array, one has to use malloc, calloc etc (as far as I know)

Your program may run fast but will not run for any size of array, mine on the other hand, will run for any size of array. Sure it may run slow but that's it.

You should not be repeatedly allocating memory - that is a substantial slow down to a sorting program.

What we have finally come across is a trade-off between space and time. Well, i chose space over time.

I found out that there is no such thing as a general quick, merge, heap ... sort. Even they are modified to suit the type and size of data they will handle.

You can try "Google Uncle" for "Library Sort"

[Adak]

The size of the original array is set with a #define statement. The secondary array is set in main(), statically. No malloc/calloc is used.

If you add the insertion sort optimization to Quicksort, you will have a much faster sorter, which uses less space than merge sort, of any kind.

I agree completely that a smart (and tested!) optimization, can help any sorting program or function.

Naturally, I've used Google quite a bit, & Wikipedia, to look for C code or pseudo code for Library sort, but come up with nothing but one fortran version. (Which does me no good, since I don't know fortran).

Oh well, I have about 15 sorting algorithms. The surprises to me were:

1) Comb11 - although it's based on bubble sort, this is a powerful sorter. Much better than the regular Comb sort program.

2) Binary Insertion - a nice improvement on straight Insertion sort. Not quite first tier, but good.

3) Quicksort with Insertion on smaller sub arrays - stomps on everything when sorting integers. Radix should be best on strings, but I haven't got to that part of the program, yet.

4) Shell sort - never a first tier sorter in the past, with the new integrated Intel cpu's, it is much improved.

The hardware is so good today, I have to frequently run a sort multiple times, with 10,000 integers or more, to get the sort to take more than 0 seconds. I am amazed! :)

[xavier666]

The secondary array is set in main(), statically. No malloc/calloc is used.

Have you made the sorting code inside a function? If yes, then are you sending the temporary array as parameter to the function?

If you add the insertion sort optimization to Quicksort, you will have a much faster sorter, which uses less space than merge sort, of any kind.

Optimization of sorting algorithms is a totally new ball game, much complex than the sorting algorithm itself. I just started sorting (1st Year in college) so I can't really discuss anything about it, however ;), I've found out that optimization again depends on the type and size of data the sorting algorithm is dealing with
I've heard that some sorting techniques are good for large amount of data. Some are good for partially sorted lists and so on...

http://www.eternallyconfuzzled.com/jsw_home.aspx
http://www.planet-source-code.com/
http://www.algorithmist.com/index.php/Main_Page
http://www.cosc.canterbury.ac.nz/mukundan/JavaP.html

You can try the above links, for your "library sort". Let me know if you find something
Cheers!