snippetcMinor
Is this an optimal implementation of merge sort?
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:
I have 2 questions:
NOTE: I tried the function using array randomly generated of length 1000 and it worked.
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
-
Memory allocation could be reduced. Via recursion, this takes > 2n (maybe 4n) memory space. At worst it should be
-
Use
-
Cope with 0 length.
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.