# Is this an optimal implementation of merge sort?

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;k<i;k++)
{
list1[k]= list[k];
list2[k]= list[i+k];
}
if(len%2!=0) list2[j-1] = list[len-1];
mergesort(list1 , i);
mergesort(list2 , j);
int k=0,l=0;
// k represent counter over elements in list1
// l represent counter over elements in list2
// k+l represent counte over total elements in list
while(k+l!=len)
{
if(k==i)
{
for(;l<j;l++) list[k+l] = list2[l];
return;
}
else if (l==j)
{
for(;k<i;k++) list[k+l] = list1[k];
}
else if(list1[k]<list2[l])
{
list[k+l]=list1[k];
k++;
}
else if(list1[k]>list2[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:

1. How can I make this implementation more optimal (best possible performance)?
2. 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.

1. 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[]

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

3. 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)

4. Cope with 0 length.

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

• I don't understand how will there be lengths of zero and what approach should I take to reduce memory allocation – oddcoder Jan 17 '15 at 8:40
• @Ahmed Abd El Mawgood 0 length example: Code has a data structure with a list of student IDs that have signed up for a class. At first, the list is empty: 0 members. It this list was sorted with mergesort(), the function should handle 0 elements. – chux - Reinstate Monica Jan 17 '15 at 15:42
• @Ahmed Abd El Mawgood True, this answer does not explain how to reduce memory. See Variants. I was not recommending that code should reduce> I was pointing out code could reduce memory. Reducing memory comes at a cost: more complex code. This code's primary problem is using too much memory from the stack using VLAs. Re-code using malloc() and free() to cope with seg fault. Then consider changes to reduce memory usage. – chux - Reinstate Monica Jan 17 '15 at 15:51