Merge Sort on Array of Int C++

Question

I'm trying to create a program merge-sort on an array of int butI keep having troubles running this merge sort, it gives me a segment fault but I couldn't find anything wrong with it. In void mergesort when I put first <= last then the segment fault appears if not, then 5 5 5 5 is being print.

#include <iostream>

 using namespace std;


void merge(int *arr, int size, int first, int middle, int last)
{
    int temp[size];
    for(int i = first; i<=last; i++)
    {
       temp[i] = arr[i];
    }
    int i=first, j=middle+1, k=0;
    while(i<=middle && j<=last)
    {
       if(temp[i] <= temp[j])
       {
          arr[k] = temp[i];
          i++;
       }
       else
       {
          arr[k]=temp[i];
          j++;
       }
       k++;
    }
    while(i<=middle)
    {
       arr[k]=temp[i];
       k++;
       i++;
    }
}

void mergesort(int *arr, int size, int first, int last)
{
    if(first<last)
    {
       int middle = ( first + last )/2;
       mergesort(arr,size,first,middle);
       mergesort(arr,size,middle+1,last);
       merge(arr,size,first,middle,last);
    }
}
int main()
{
    cout <<"Him";
    const int size = 10;
    int numbers [] = {5,10,1,6,2,9,3,8,7,4};
    mergesort(numbers,size,0,9);
    for( int i= 0; i<size; ++i)
    {
        cout << numbers[i] << " ";
    }
    return 0;
}

Use vectors, which are bounds-checked on good compilers, to find where you overrun. If you aren't allowed to use vectors, then convert back to regular arrays when you are done. — Neil Kirk, Apr 13 '15 at 23:56

score 2 · Accepted Answer · answered Apr 14 '15 at 02:33

There are (at least) two bugs. This:

else
{
   arr[k]=temp[i];                                          
   j++;
}

should be this:

else
{
   arr[k]=temp[j];                                          
   j++;
}

and this:

int i=first, j=middle+1, k=0;

should be this:

int i=first, j=middle+1, k=first;

In general, you ought to learn to step through the code, at least by putting diagnostic output statements here and there. Once you have the hang of that you can move up to a good debugger.

score 1 · Answer 2 · answered Mar 06 '18 at 09:47

The standard library already implements a function that merges correctly: std::inplace_merge. Implementation adapted from this more general post

void mergesort(int * first, int * last)
{
    std::ptrdiff_t N = std::distance(first, last);
    if (N <= 1) return;                   
    int * middle = std::next(first, N / 2);
    mergesort(first, middle); 
    mergesort(middle, last);  
    std::inplace_merge(first, middle, last); 
}

int main()
{
    cout <<"Him";
    const int size = 10;
    int numbers [] = {5,10,1,6,2,9,3,8,7,4};
    mergesort(numbers, numbers+size);
    for( int i= 0; i<size; ++i)
    {
        cout << numbers[i] << " ";
    }
    return 0;
}

erol yeniaras · Answer 3 · 2015-04-14T02:26:39.280

0

Suggestion 1:

Instead of that line:

int temp[size];

If you need a dynamic size array use:

int temp = new int[size];

Then once you are done with it

delete[] temp;

Edit: As Neil suggested using std::vector is may be more useful than arrays in such situations (if you are allowed to use it).

edited Apr 14 '15 at 02:26

answered Apr 14 '15 at 02:05

erol yeniaras

3,701
2
22
40

3

Suggestion 0: `std::vector temp(size);` – Neil Kirk Apr 14 '15 at 02:09
Why construct the array on the heap? What's the advantage? – Beta Apr 14 '15 at 02:14
@Beta: it has nothing to do with advantage here. We cannot create dynamic size array in the stack but a merge sort algorithm should support the arrays of variable sizes in my opinion. The size is constant here as 10 but what if user input some other array with different size or this merge method needs to be used somewhere else where the array size is not constant? Therefore it is always more flexible to use either std::vector or dynamic size array (heap array). – erol yeniaras Apr 14 '15 at 02:20
You're right that VLAs are not legal in C++, I'd forgotten about that. But the OP appears to be using a compiler that allows them (or the code would not compile), and if the compiler allows them then this `merge` will work (once the bugs are fixed). Whether it is called with the same `size` every time makes no difference. – Beta Apr 14 '15 at 02:49
Well, mine was just a suggestion. It might be a good option to write c++ code independent of platform so that it can be used anytime anywhere. – erol yeniaras Apr 14 '15 at 02:55

score 0 · Answer 4 · answered Mar 06 '18 at 07:48

Your code has 3 bugs, Also you can reduce your code length too if required.

void merge(int *arr, int size, int first, int middle, int last)
{
    int temp[size];
    for(int i = first; i<=last; i++)
      temp[i] = arr[i];
    int i=first, j=middle+1, k=first; // 1st Change, Set k to first instead of 0
    while(i<=middle && j<=last)
    {
       if(temp[i] <= temp[j])
          arr[k++] = temp[i++];
       else
          arr[k++]=temp[j++]; // 2nd Change, use j instead of i
    }
    while(i<=middle)
       arr[k++]=temp[i++];
    while(j<=last)    // 3rd Change you missed this case
        arr[k++]=temp[j++];
}

Live Code

Merge Sort on Array of Int C++

4 Answers4