3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$
  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;
    
\$\endgroup\$
3
  • \$\begingroup\$ I don't understand how will there be lengths of zero and what approach should I take to reduce memory allocation \$\endgroup\$ – oddcoder Jan 17 '15 at 8:40
  • \$\begingroup\$ @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. \$\endgroup\$ – chux - Reinstate Monica Jan 17 '15 at 15:42
  • \$\begingroup\$ @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. \$\endgroup\$ – chux - Reinstate Monica Jan 17 '15 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.