2
#include <stdio.h>

void mergesort();
void merge();

int main()
{
    int a[40], n;
    printf("\nEnter the number of elements:");
    scanf("%d", &n);
    printf("\nEnter the %d elements:", n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }
    mergesort(a, 0, n - 1);
    printf("\nThe Sorted array is: ");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}

void mergesort(int a[], int first, int last)
{
    int mid;
    if (first < last)
    {
        mid = (mid + last) / 2;
        mergesort(a, first, mid);
        mergesort(a, mid + 1, last);
        merge(a, first, mid, last);
    }
}

void merge(int a[], int first, int mid, int last)
{
    int b[50];
    int i, j, k;
    i = first;
    j = mid + 1;
    k = first;
    while (i <= mid && j <= last)
    {
        if (a[i] <= a[j])
            b[k++] = a[i++];
        else
            b[k++] = a[j++];
    }
    if (i > mid)
    {
        while (j <= last)
            b[k++] = a[j++];
    }
    else
    {
        while (i <= mid)
            b[k++] = a[i++];
    }
    for (i = first; i <= last; i++)
        a[i] = b[i];
}

I have written this Merge Sort program in C. It shows "Segmentation fault (core dumped)" after implementation of arrays. I don't know what is the issue. So please help me out i have exam on the next day. I get output like this

Enter the number of elements:5

Enter the 5 elements:1 2 3 5 4 Segmentation fault (core dumped)

It was found that I made a mistake while implementing mid variable. The correct one is:

mid=(first+last)/2;

Thank you all for your helps. Each and every of your replies were useful in identifying the error.

mch
  • 9,424
  • 2
  • 28
  • 42
ProblemChild
  • 23
  • 4
  • Try following the execution using your debugger. Are the values of `i`, `j` and `k` always inside the correct bounds? – Bob__ Aug 09 '22 at 14:20
  • 2
    `mid = (mid + last) / 2;` : here `mid` has never been initialized. The initial value of `mid` is indetermined. Your code has undefined behaviour. – Jabberwocky Aug 09 '22 at 14:26
  • Thank you @Jabberwocky . I had to write first instead of mid . – ProblemChild Aug 09 '22 at 14:34
  • Have you tried running your code line-by-line in a debugger while monitoring the values of all variables, in order to determine in which line your program stops behaving as intended? If you did not try this, then you may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) – Andreas Wenzel Aug 09 '22 at 15:05

2 Answers2

3

The program has undefined behavior since you read mid when it's uninitialized:

void mergesort(int a[], int first, int last) {
    int mid;
    if (first < last) {
        mid = (mid + last) / 2;
//             ^^^

You probably want:

        mid = (first + last) / 2;
Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108
1
void mergesort(int a[],int first,int last)
{
 int mid;
 if(first<last)
 {
  mid=(mid+last)/2;
  mergesort(a,first,mid);
  mergesort(a,mid+1,last);
  merge(a,first,mid,last);
 }
}

When this runs the first time, mid is not guaranteed to be 0 or any other number; mid is some integer that may change every time. Thus, the number you are getting may be well outside the bounds of the array. Initializing mid to 0 would fix that, but as the answers above me point out you actually want to do mid = (first + last) / 2

TarHalda
  • 1,050
  • 1
  • 9
  • 27
  • I don't think that'll work. It'll be the same as doing `mid = last / 2;` Did you try it? – Ted Lyngmo Aug 09 '22 at 14:41
  • 1
    Good point. It will at least stop him from getting garbage instead, but I'll edit my answer to point out that initializing mid won't solve the real problem. @TedLyngmo – TarHalda Aug 09 '22 at 14:49