I just received the MERGE SORT code from my friend, here it is
void sort_merge (int *array, int low, int high)
{
int mid;
if (low < high)
{
mid = (low + high) / 2;
sort_merge (array, low, mid);
sort_merge (array, mid + 1, high);
array_merge (array, low, high, mid);
}
}
void array_merge (int *array, int low, int high, int mid)
{
int i = low;
int j = mid + 1;
int k = low;
int array_temp[50];
while (i <= mid && j <= high)
{
if (array[i] < array[j])
{
array_temp[k++] = array[i++];
}
else
{
array_temp[k++] = array[j++];
}
}
while (i <= mid)
{
array_temp[k++] = array[i++];
}
while (j <= high)
{
array_temp[k++] = array[j++];
}
for (i = low; i < k; i++)
{
array[i] = array_temp[i];
}
}
It's running okay, however, it has a problem. You'll see that in array_merge, it has declared array_temp[50] and
hence, it is static. If size of array is small, this program becomes inefficient and if
size of array is large, this won't work. So i made a modification, that is,
printed the values of low, high & k
void array_merge (int *array, int low, int high, int mid)
{
int i = low;
int j = mid + 1;
int k = low;
int array_temp[50];
while (i <= mid && j <= high)
{
if (array[i] < array[j])
{
array_temp[k++] = array[i++];
}
else
{
array_temp[k++] = array[j++];
}
}
while (i <= mid)
{
array_temp[k++] = array[i++];
}
while (j <= high)
{
array_temp[k++] = array[j++];
}
printf("\n\n\t\tLENGTH OF ARRAY - %d\tLOW - %d\tHIGH - %d", k, low, high); // THE CHANGED PORTION
for (i = low; i < k; i++)
{
array[i] = array_temp[i];
}
}
Here is the output
SIZE OF ARRAY = 10
INPUT - 10,1,9,2,8,3,7,4,6,5
LENGTH OF ARRAY - 2 LOW - 0 HIGH - 1
LENGTH OF ARRAY - 3 LOW - 0 HIGH - 2
LENGTH OF ARRAY - 5 LOW - 3 HIGH - 4
LENGTH OF ARRAY - 6 LOW - 3 HIGH - 5
LENGTH OF ARRAY - 6 LOW - 0 HIGH - 5
LENGTH OF ARRAY - 8 LOW - 6 HIGH - 7
LENGTH OF ARRAY - 9 LOW - 6 HIGH - 8
LENGTH OF ARRAY - 11 LOW - 9 HIGH - 10
LENGTH OF ARRAY - 11 LOW - 6 HIGH - 10
LENGTH OF ARRAY - 11 LOW - 0 HIGH - 10
By printing the value of 'k', i know what the maximum value of the size of array_temp can be.
By observation, i saw that 'k = high + 1' for each time it is called
So i again modified my program, by making the memory allocation of 'array_temp' dynamic
void array_merge (int *array, int low, int high, int mid)
{
int i = low;
int j = mid + 1;
int k = low;
int *array_temp = (int *)calloc(high + 1, sizeof(int)); // DYNAMIC ALLOCATION
while (i <= mid && j <= high)
{
if (array[i] < array[j])
{
array_temp[k++] = array[i++];
}
else
{
array_temp[k++] = array[j++];
}
}
while (i <= mid)
{
array_temp[k++] = array[i++];
}
while (j <= high)
{
array_temp[k++] = array[j++];
}
for (i = low; i < k; i++)
{
array[i] = array_temp[i];
}
free(array_temp);
}
But the problem with this is that when i sort and print the array, the array elements gets deleted
I just can't understand what the problem is. Some help would be greatly appreciated
By the way, this problem gets solved if i write int *array_temp = (int *)malloc(sizeof(array));
But I think there is a better solution
Thanks, in advance!