Home > Software engineering >  Merge sort not printing sorted array
Merge sort not printing sorted array

Time:10-24

My code here gets terminated after printing the unsorted array and also gives runtime error on ideone , i am unable to find the error in it . code works fine until the first mergesort in function but gets terminated afterwards without executing merge function . I have tried changing array size but nothing has worked so far . Any help would be appreciated.

#include<stdio.h>
#include<math.h>
void Merge(int arr[],int,int,int,int);

void printArray(int *arr,int n)
{
    for (int i = 0; i < n; i  )
    {
        printf("%d",arr[i]);
        printf(" ");
    }
    printf("\n");
}

void MergeSort(int arr[],int low,int high)
{
    
    int mid;
    if(low<high)
    {
       
        mid = ceil((low high)/2);
      
        MergeSort(arr,low,mid-1);
        
        MergeSort(arr,mid,high);
     
        Merge(arr,low,mid-1,mid,high);
    }
}

void Merge(int arr[],int low,int mid1,int mid2, int high)
{
    
    int i,c,j;

    c = low;
    i = low;
    j  = mid2;

    int Temp[high-low 1];
    while(i <= mid1 && j<= high)
    {
        if(arr[i]<arr[j])
        {
            Temp[c] = arr[i];
            i  ;
            c  ;
        }
        else
        {
            Temp[c] = arr[j];
            j  ;
            c  ;
        }
    }    

    while(i<=mid1)
    {
        Temp[c] = arr[i]; 
        i  ;
        c  ;          
    }
    while(j<=high)
    {
        Temp[c] = arr[j]; 
        j  ;
        c  ;
    }
    
    for(int k=0;k<=high;k  )
    {
        arr[k] = Temp[k];
    }    
    
}

int main(void)
{
    int arr[] = {3,5,2,13,12,3,2,13,45};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("unsorted array: \n");
    printArray(arr,n);
    MergeSort(arr,0,n-1);
    printf("sorted array: \n");
    printArray(arr,n);
    return 0;

}

CodePudding user response:

There are several issues:

  • ceil is not useful as / will perform an integer division and so has already rounded down
  • Related to this, you should not use mid-1 and mid as arguments in the next recursive calls, but mid and mid 1. The same should be done with the arguments to Merge.
  • The way you access Temp is wrong. You allocate entries from 0 to high-low, but start your access with a value of c that is low. You should instead start at index 0.
  • In the very last loop k runs from 0 to high, but that are too many iterations. It should start from low, and then the index access to Temp should again be adapted by using k-low as index.

Here is the corrected code:

void MergeSort(int arr[],int low,int high)
{
    int mid;
    if(low<high)
    {
        mid = (low high)/2; // <--
        MergeSort(arr,low,mid); // <--
        MergeSort(arr,mid 1,high); // <--     
        Merge(arr,low,mid,mid 1,high); // <--
     }
}

void Merge(int arr[],int low,int mid1,int mid2, int high)
{   
    int i,c,j;
    c = 0; // <--
    i = low;
    j  = mid2;

    int Temp[high-low 1];
    while(i <= mid1 && j<= high)
    {
        if(arr[i]<arr[j])
        {
            Temp[c] = arr[i];
            i  ;
            c  ;
        }
        else
        {
            Temp[c] = arr[j];
            j  ;
            c  ;
        }
    }    
    while(i<=mid1)
    {
        Temp[c] = arr[i]; 
        i  ;
        c  ;          
    }
    while(j<=high)
    {
        Temp[c] = arr[j]; 
        j  ;
        c  ;
    }
    for(int k=low;k<=high;k  ) // <--
    {
        arr[k] = Temp[k-low]; // <--
    }
}

Important note: I debugged the code for you, but this is something you can do yourself. Inspect the variables as you step through the code with a debugger, and spot where things are unexpected. It takes some time, but it is a skill a coder needs to learn.

  • Related