Why am I getting a segmentation fault?

Question

If I pass a value greater than 100 as the second argument to BinaryInsertionSort, I get a segmentation fault.

int
BinarySearch (int a[], int low, int high, int key)
{
    int mid;

    if (low == high)
        return low;

    mid = low + ((high - low) / 2);

    if (key > a[mid])
        return BinarySearch (a, mid + 1, high, key);
    else if (key < a[mid])
        return BinarySearch (a, low, mid, key);

    return mid;
}

void
BinaryInsertionSort (int a[], int n)
{
    int ins, i, j;
    int tmp;

    for (i = 1; i < n; i++) {
        ins = BinarySearch (a, 0, i, a[i]);
        if (ins < i) {
            tmp = a[i];
            memmove (a + ins + 1, a + ins, sizeof (int) * (i - ins));
            a[ins] = tmp;
        }
    }
}

Answer 1

Could be because of stack overflow? You're calling BinarySearch recursively. The greater the value of n, the more stack space you'll consume. I would expect that you'd see a stack overflow error in such a case, but I don't know your environment...

Assuming that you aren't using a debugger, a quick way to test this would be to first find the exact point at which you get the error (you mentioned 100, but it's not clear that you wouldn't get the error with 99...).

Once you have that, try increasing the amount of stack space consumed by each recursive call to BinarySearch (add a few additional local variables, and do enough with them that they won't be optimized out). You should see that you can no longer successfully do 99 (or whatever your previous maximum was).

Answer 2

Hard to tell, Use a debugger. It will help you locate where the segmentation fault is located, and what are the value of different variable when the segmentation fault occurs.

• on linux: gdb (to compile use g++ with the -g option)
• on windows: the integrated debugger of visual studio C++

Answer 3

You are passing an array a[] in. it must be large enough that the values hi and low are in range.

For example, if you pass an array of size 1 in, and low = 0. hi = 2, then mid = 1 which will be out of range (an array of size 1 can only have a[0] dereferenced, a[1] will be out of range).