Question

Iterative Merge Sort is not working

#include
#include
#include
int* b;
void merge(int a[], int left, int mid, int right)
{
   int i = left, j = mid + 1, k = left;

   while (i <= mid && j <= right)
   {
       if (a[i] < a[j])
           b[k++] = a[i++];
       else
           b[k++] = a[j++];
   }
   for (; i <= mid; i++)
   {
       b[k++] = a[i];
   }
   for (; j <= right; j++)
   {
       b[k++] = a[j];
   }
   for (int i = left; i <= right; i++)
   {
       a[i] = b[i];
   }

}
void mergesort(int a[], int n)
{
   int p, left, right, mid, i;
   for (p = 2; p <= n; p = p * 2)
   {
       for (i = 0; i + p - 1 < n; i = i + p)
       {
           left = i;
           right = i + p - 1;
           mid = (left + right) / 2;
           merge(a, left, mid, right);
       }
   }
   if (p / 2 < n)
   {
       merge(a, 0, (p / 2) - 1, n - 1);
   }
}
void main()
{
   int max, * a;
   scanf("%d", &max);
   a = (int*)malloc(sizeof(int) * max);
   b = (int*)malloc(sizeof(int) * max);
   for (int i = 0; i < max; i++)
   {
       scanf("%d", &a[i]);
   }
   mergesort(a, max);
   for (int i = 0; i < max; i++)
   {
       printf(" %d", a[i]);
   }
}

input 50

50 49 48 47 46 45 ~ 5 4 3 2 1

output

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 2 19 20 21 22 23 24 ~ 50

why 1,2 are between in 18 and 19?

please answer and correct code

Answer 1

#include <stdio.h>
#include<iostream>

int* b;
void m(int a[], int l1, int m1, int r1)
{
int i = l1, j = m1 + 1, q = l1;//intialise the values

while (i <= m1 && j <= r1)//iterate until one of the array finished
{
if (a[i] < a[j])//compare both sub sorted array values
b[q++] = a[i++]; //update to new array
else
b[q++] = a[j++]; //compare both sub sorted array values and update to new array
}
for (; i <= m1; i++)//iterate until large sub array is finished
{
b[q++] = a[i]; //update to new array
}
for (; j <= r1; j++) //iterate until large sub array is finished
{
b[q++] = a[j]; //update to new array
}
for (int i = l1; i <= r1; i++)//copy new array to old array
{
a[i] = b[i];
}

}
void msort(int a[], int n)
{
int p, l1, r1, m1, i;//initialised
for (p = 2; p <= n; p = p * 2)//step size for loop this is 2 times
{
for (i = 0; i + p - 1 < n; i = i + p) //step size for loop this is 3,5,7.... times
{
l1 = i;
r1 = i + p - 1;
m1 = (l1 + r1) / 2;
m(a, l1, m1, r1);
}
}
if (p / 2 < n)
{
m(a, 0, (p / 2) - 1, n - 1);
}
}
void main()
{
int max, * a;//variables
scanf("%d", &max);//getting value of array size
a = (int*)malloc(sizeof(int) * max);//creating array
b = (int*)malloc(sizeof(int) * max);//creating array
for (int i = 0; i < max; i++)
{
scanf("%d", &a[i]);//getting values from user
}
msort(a, max); //calling sort function
for (int i = 0; i < max; i++)
{
printf(" %d", a[i]);//printing the values if sorted array
}
}

in this as loop start with p=2 it will sort all the 2 elements start with 50 49 47 48 45 46,,,,,,,2 1 and after p=3 it going to sort 3 elements 47 49 50 48 45 46,,,,,,,2 1 and in this way it will the whole list and it result into neglect last 2 elemets and they sort at some value of p in between and in that 1 and 2 become before all the sort element that why it comes after 18 in your output.

If you found this answer helpful please give a thumbs up.