Is this an optimal implementation of merge sort?

Question

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.

Answer 1

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;
   

• u185619: I don't understand how will there be lengths of zero and what approach should I take to reduce memory allocation
• chux: @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: @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.