#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>
#include <time.h>
void DISPLAY(int*, int);
int* MERGE(int*, int, int* , int, int* , int );
int* MERGESORT(int* , int );
int main()
{
int* array = NULL;
array = (int*) malloc(7 * sizeof(int) );
array[0] = 10;
array[1] = 9;
array[2] = 8;
array[3] = 57;
array[4] = 6;
array[5] = 5;
array[6] = 24;
printf("\nOriginal array: \n");
DISPLAY(array, 7);
array = MERGESORT(array, 7);
printf("\n\nResulting array: \n");
DISPLAY(array, 7);
}
void DISPLAY(int* array, int size)
{
int i;
for(i = 0; i < size; i++){
printf("%d ", array[i]);
}
}
int* MERGESORT(int *array, int size) {
if(size < 2)
return array;
int mid = size / 2;
int rightsize = size-mid;
int* L = (int*) malloc(mid * sizeof(int));
int* R = (int*) malloc((size-mid) * sizeof(int));
int i;
for(i = 0; i < mid; i++)
L[i] = array[i];
for(i = mid; i < size; i++)
R[i-mid] = array[i];
L = MERGESORT(L, mid);
R = MERGESORT(R, size-mid);
array = MERGE(array, size, L, mid, R, rightsize);
free(L);
free(R);
return array;
}
int* MERGE(int *array, int size, int *L, int leftsize,int *R, int rightsize) {
int i, j, k;
i = 0;
j = 0;
k = 0;
while(i < leftsize && j < rightsize)
{
if(L[i] < R[j])
{
array[k] = L[i];
i++;
}
else{
array[k] = R[j];
j++;
}
k++;
}
while(i < leftsize)
{
array[k] = L[i];
i++;
k++;
}
while(j < rightsize)
{
array[k] = L[j];
j++;
k++;
}
printf("\nUpdated array: \n");
DISPLAY(array, size);
return array;
}
Hello, I have a problem when I try to perform merge sorting in an array. Some items in the array are printing weird. Every time the arrays get updated, the value gets printed out, but it doesn't work at specific inputs.
When I input small numbers (like 1-2 digits), then the array gets sorted normally.
Sample run of program sorting incorrectly: https://i.sstatic.net/OLg0b.png
a = malloc(n * sizeof *a), you can only reference a[0] through a[n-1].malloc((size-mid) * sizeof(int))why not userightsizeinstead ofsize - mid? Same when you callMERGESORT(R, size-mid). I also recommend you start to use unsigned types for sizes and indexes, preferablysize_t.