Segmentation Fault, Merge Sort algortihm

Question

This is a merge- sort algorithm I wrote. Although, it works well for smaller arrays, it gives a segmentation fault for arrays containing more than 7/8 elements. It also fails in some cases where a number is repeated. For example - {5,5,1,2,1}. I have been trying to identify the error but to no avail

I know that the code is not completely efficient but I am concentrating on making it work right now. Suggestions regarding the improvements in the code will be helpful. Thank you in advance.

#include <iostream>
using namespace std;
void printarray(int a[], int size);
void splitsort(int b[], int start, int end); //Split array into half
void merge(int b[], int start, int end); // merge the sorted arrays

int main()
{
    cout << "This is merge sort" << endl;
    int array[] = { 9,8,7,6,5,4,3,2,1 };
    int length = sizeof(array) / sizeof(array[0]);
    printarray(array, length);
    splitsort(array, 0, length - 1);
    cout << "sorted array" << endl;
    printarray(array, length);
    return 0;
}

void printarray(int a[], int size) {
    for(int i = 0; i<size; i++) {
        cout << a[i] << ",";
    }
    cout << endl;
    return;
}

void splitsort(int b[], int start, int end) {
    //base case
    if(end == start) { return; }

    //
    splitsort(b, start, (start + end) / 2);
    splitsort(b, (start + end) / 2 + 1, end);
    merge(b, start, end);

    return;
}

void merge(int b[], int start, int end) {
    int tempb[(end - start) + 1];

    //base case
    if(end == start) { return; } // if single element being merged
    int i = start;
    int j = (start + end) / 2 + 1;
    for(int k = start; k <= end; k++) {
        if(i == (start + end) / 2 + 1) { tempb[k] = b[j]; j++; }// finished first array
        else if(j == end + 1) { tempb[k] = b[i]; i++; }// finished second array
        else if(b[i] >= b[j]) {
            tempb[k] = b[j];
            j++;
        }
        else if(b[j] >= b[i]) {
            tempb[k] = b[i];
            i++;
        }
    }

    for(int k = start; k <= end; k++) {
        b[k] = tempb[k];
    }

    return;
}

*it gives a segmentation fault for bigger arrays* Define bigger — Gaurav Sehgal, Jul 15 '18 at 03:31
Sorry for not being specific. Basically it sorts the arrays containing upto 6,7 members. It fails some cases wherein a number is repeated multiple times. For example - It doesn't sort {5,5,1,2,1} correctly. — Steph, Jul 15 '18 at 03:34
Where does it segfault? Have you debugged it? Use gdb and step through your program to see what is going wrong. SO is a not free debugging service. — , Jul 15 '18 at 03:37
Thank you for your suggestion. I'm just beginning to code and don't exactly understand what you mean. If this is something which is not in line with the guidelines of SO, I'm sorry. — Steph, Jul 15 '18 at 03:40
`int tempb[(end-start)+1];` is not legal C++. `b[k]=tempb[k];` is wrong, `temp` and `b` have different bounds. — n. m. could be an AI, Jul 15 '18 at 03:46
@ n.m- Do you mind expanding on your comment? What would be the best way to represent the temporary array? — Steph, Jul 15 '18 at 03:54
@Steph, debug your code using gdb or VS debugger first. If you then get any error, post your query. Its an important skill — Gaurav Pant, Jul 15 '18 at 03:56
I treid using an online debugger and it says Program received signal SIGSEGV, Segmentation fault. Also, the mistake is shown for b[k]=tempb[k];. Can I know why this is not legal C++? I have used this kind of assignment before in some codes and it worked fine. — Steph, Jul 15 '18 at 04:10
Stack Overflow isn't a free debugging service, and you should show your attempts at debugging the code with a debugger or other simpler methods such as debug print statements. You can also test each part of the code separately to figure out exactly which part of the code is causing the problem, and make a [mcve]. This won't be the only time you end up with a bug in your code, and learning to debug your programs will help you much more than having someone find the bug for you. http://idownvotedbecau.se/nodebugging/ — eesiraed, Jul 15 '18 at 04:16
C++ doesn't have variable length arrays, and the size of an array must be a compile-time constant. Your code only compiles because of a GCC non-standard extension. See https://stackoverflow.com/q/22013444/9254539 If you need an array with an unknown length, you should use an `std::vector`. When the program segfaulted in the debugger, it should have shown you exactly where the segfault happened. That's the time to inspect the value of variables, and maybe step through the program execution before the segfault. — eesiraed, Jul 15 '18 at 04:18
@Steph -- Quit using raw arrays. Make all arrays either `std::vector` or `std::array`. Then you have a better chance of fixing your own errors, since you can now do bounds-checking on the accesses you're doing by using `at()` instead of `[ ]`. If you want proof, [see here](http://coliru.stacked-crooked.com/a/563f731e1c0f1b5c). No segmentation fault -- instead you get an exception that tells you what the issue is. You just need to find which `at()` call triggered the error and fix the issue. — PaulMcKenzie, Jul 15 '18 at 05:05

score 1 · Answer 1 · answered Jul 15 '18 at 08:10

int tempb[(end - start) + 1];

tempb can have as few as 2 elements, while the main array has 10 elements. You end up accessing tempb[9], causing segmentation fault.

To fix the problem, change the size to int tempb[max_size]; where max_size is the size of array as calculated earlier int length = sizeof(array) / sizeof(array[0]);

Changing tempb to std::vector<int> tempb(max_size) will help in debugging as well as being compliant with C++ standard.

Segmentation Fault, Merge Sort algortihm

1 Answers1