mergesort2.c #include <stdio.h> void mergesort(int* array, int lower, int upper)

Question

mergesort2.c

#include <stdio.h>

void mergesort(int* array, int lower, int upper);
void merge(int* array, int lower, int middle, int upper);

int main(void) {
int len;
int *p;

printf("Enter the length of the array: ");
scanf("%d", &len);

int array[len];

printf("Enter %d integers: ", len);

for (p = array; p < array+len; p++)
    scanf("%d", ________);

mergesort(array, 0, len-1);

printf("The sorted array is: ");
for (p = array; p < array+len; p++) {
    printf("%d", _________);
    if (p < array + len - 1)
      printf(" ");
}
printf(" ");

return 0;
}

void mergesort(int* array, int lower, int upper) {
if (lower < upper) {
    int middle = (lower + upper) / 2;
    mergesort(array, lower, middle);
    mergesort(array, middle+1, upper);
    merge(array, lower, middle, upper);
}
}

void merge(int* array, int lower, int middle, int upper) {
int len_left = middle - lower + 1;
int len_right = upper - middle;
int left[len_left], right[len_right];
int *p, *q, *r;

for (p = left, r = array + lower; p < left + len_left; p++, r++)
    *p = *r;

for (q = right; q < right + len_right; q++, r++)
    *q = *r;

p = left;
q = right;
r = array + lower;

while (p < left + len_left && q < right + len_right) {
    if (*p <= *q)
      *r++ = *p++;
    else
      *r++ = _________;
}

while (p < left + len_left)
    *r++ = *p++;

while (q < _________________)
    *r++ = *q++;
}

Explanation / Answer

void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int num1 = m - l + 1;
int num2 = r - m;
int Left[num1], Right[num2];
for (i = 0; i < num1; i++)
L[i] = arr[l + i];
for (j = 0; j < num2; j++)
R[j] = arr[m + 1+ j];

  
i = 0;
j = 0;
k = l;
while (i < num1 && j < num2)
{
if (Left[i] <= Right[j])
{
arr[k] = Left[i];
i++;
}
else
{
arr[k] = Right[j];
j++;
}
k++;
}

while (i < num1)
{
arr[k] = Left[i];
i++;
k++;
}

  
while (j < num2)
{
arr[k] = Right[j];
j++;
k++;
}
}

void mergeSort(int arr[], int l, int r)
{
if (l < r)
{

int m = l+(r-l)/2;

mergeSort(arr, l, m);
mergeSort(arr, m+1, r);

merge(arr, l, m, r);
}
}

void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf(" ");
}

int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);

printf("Given array is ");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf(" Sorted array is ");
printArray(arr, arr_size);
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.