HiveBrain v1.2.0
Get Started
← Back to all entries
snippetcMinor

Is this an optimal implementation of merge sort?

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
thisoptimalmergesortimplementation

Problem

I am taking an algorithm course and we are to implement merge sort that handles list of elements with even or odd number of elements and handles duplication, so I wrote this function:

void mergesort (int* list, int len)
{
        if(len == 1) return;
        int i = len/2, j = len-i;
        int list1[i], list2[j];
        for(int k=0;klist2[l])
                {
                        list[k+l] = list2[l];
                        l++;
                }
                else
                {
                //handles dublication
                list[k+l] = list1[k];
                k++;
                list[k+l] = list[l];
                l++;
                }
        }
}


I have 2 questions:

  • How can I make this implementation more optimal (best possible performance)?



  • When handling arrays of large lengths (1000000), what causes a segmentation fault?



NOTE: I tried the function using array randomly generated of length 1000 and it worked.

Solution

-
Suspect that segmentation fault on large arrays occurs because the list1[] and list2[] ran out of space. With the recursive calls, code is heavily using the stack space. Use malloc() and free() for large arrays instead of VLA[]

-
Memory allocation could be reduced. Via recursion, this takes > 2n (maybe 4n) memory space. At worst it should be 2n.

-
Use size_t rather than int for a integer type that can handle all array indexes.

// void mergesort (int* list, int len)
void mergesort (int* list, size_t len)


-
Cope with 0 length.

// if(len == 1) return;
if(len <= 1) return;

Code Snippets

// void mergesort (int* list, int len)
void mergesort (int* list, size_t len)
// if(len == 1) return;
if(len <= 1) return;

Context

StackExchange Code Review Q#77707, answer score: 2

Revisions (0)

No revisions yet.