patterncMinor
Implementation of mergesort in C
Viewed 0 times
implementationmergesortstackoverflow
Problem
I have implemented mergesort in C. Any advice on making it more compact? My merge function seems less than fully optimal.
//mergeSort in C
#include
#include
void merge(int [], int[], int[], int, int);
void mergesort(int[], int);
int main()
{
int unsorted[] = {4, 1, 3, 0, 10, 2, 5, 5};
int size = sizeof(unsorted)/sizeof(int);
mergesort(unsorted, size);
printf("The sorted array is: ");
for(int i = 0; i < size; i++)
{
printf("%d, ", *(unsorted+i));
}
return 0;
}
void merge(int *original, int* first, int* second, int len1, int len2)
{
int i = 0;
int firPtr = 0;
int secPtr = 0;
while(i < (len1+len2))
{
if(firPtr == len1)
{
original[i] = second[secPtr++];
}
else if(secPtr == len2)
{
original[i] = first[firPtr++];
}
else if(first[firPtr] < second[secPtr])
{
original[i] = first[firPtr++];
}
else
{
original[i] = second[secPtr++];
}
i++;
}
}
void mergesort(int unsorted[], int size)
{
if(size <= 1 || unsorted == NULL)
{
return;
}
int *first = (int *)malloc((size/2)*sizeof(int));
int *second = (int *)malloc((size - size/2)*sizeof(int));;
int mid = size/2;
for(int i = 0; i < mid; i++)
{
*(first+i) = *(unsorted+i);
}
//Common Error/Note to self: Make sure when initializing j to
//not 0, the code block truly requires that.
for(int j = (mid); j < size; j++)
{
*(second+(j-mid)) = *(unsorted+j);
}
mergesort(first, mid);
mergesort(second, size - mid);
merge(unsorted, first, second, mid, size - mid);
free(first);
free(second);
}Solution
Taking memory into consideration:
That code uses \$(n*log(n))\$
This code makes it n
That code uses \$(n*log(n))\$
sizeof(int) bytes of heap memory for array elements storage.This code makes it n
sizeof(int). By creating temporary memory only once and passing it to other functions, it saves significant memory in case of large arrays./* sorts given input array in ascending order */
void merge_sort (int * arr,int size)
{
int *temp;
if((temp = (int*)malloc(sizeof(int)*size))!=NULL)
msort(arr,temp,0,size-1) ;
}
void msort(int * arr,int * temp,int first,int last)
{
if (first>= last) return ;
int split = (first+last) / 2 ;
msort(arr,temp,first,split) ;
msort(arr,temp,split+1,last) ;
merge(arr,temp,first,split,last) ;
}
void merge (int * arr,int *temp,int f_start,int f_end,int s_end)
{
/* s_start == f_end+1 */
int i = f_start ;
int j = f_end+1 ;
int k = f_start ;
while (i<=f_end && j<=s_end)
{
if (arr[i]<arr[j])
temp[k++] = arr[i++] ;
else
temp[k++] = arr[j++] ;
}
while (i<=f_end)
temp[k++] = arr[i++] ;
while (j<=s_end)
temp[k++] = arr[j++] ;
for (i=f_start ; i<=s_end ; i++)
{
arr[i] = temp[i] ;
}
}Code Snippets
/* sorts given input array in ascending order */
void merge_sort (int * arr,int size)
{
int *temp;
if((temp = (int*)malloc(sizeof(int)*size))!=NULL)
msort(arr,temp,0,size-1) ;
}
void msort(int * arr,int * temp,int first,int last)
{
if (first>= last) return ;
int split = (first+last) / 2 ;
msort(arr,temp,first,split) ;
msort(arr,temp,split+1,last) ;
merge(arr,temp,first,split,last) ;
}
void merge (int * arr,int *temp,int f_start,int f_end,int s_end)
{
/* s_start == f_end+1 */
int i = f_start ;
int j = f_end+1 ;
int k = f_start ;
while (i<=f_end && j<=s_end)
{
if (arr[i]<arr[j])
temp[k++] = arr[i++] ;
else
temp[k++] = arr[j++] ;
}
while (i<=f_end)
temp[k++] = arr[i++] ;
while (j<=s_end)
temp[k++] = arr[j++] ;
for (i=f_start ; i<=s_end ; i++)
{
arr[i] = temp[i] ;
}
}Context
StackExchange Code Review Q#115976, answer score: 2
Revisions (0)
No revisions yet.