Segmentation Fault (merge sort)

[enduser000]

Hello,
I had a lab today for a CS class and it took awhile. At first I was having simple issues that came from my misunderstanding of how he wanted us to implement the sort, but later he started helping me and we ran into an issue that neither of us could solve. It says 'Segmentation Fault' whenever you run the program, even if you comment out most of main. I booted into windows and it compiled and ran fine under netbeans/mingw. I'll post the code below, does anyone know why this would happen? (oh and we also rewrote merge() to see if that was the problem, it wasn't)

// main82.cpp
// Lab 8 part 2...mergesort a random array


#include <cstdlib>
#include <iostream>
using namespace std;

void generateArray(int a[], int n);
void merge(int a[], int f1, int l1, int f2, int l2);
void mergesort(int a[], int first, int last);
void dumpArray(int a[], int first, int last);

// const int ARRAYSIZE = 32;
const int ARRAYSIZE = 4;
const int SEED = 12112131;

int main() {

    int a[ARRAYSIZE];
    generateArray(a, ARRAYSIZE);
    cout << endl;
    cout << "-------Original array-------" << endl;
    dumpArray(a, 0, ARRAYSIZE - 1);

    mergesort(a, 0, ARRAYSIZE - 1);

    cout << endl;
    cout << "-----Here's the sorted array-----" << endl;
    dumpArray(a, 0, ARRAYSIZE - 1);

    cout << "made it";
    cout << endl;
    cout << "made it";
    // system("PAUSE");
    return EXIT_SUCCESS;
}

// Generate an array of unique ints in [0,10n-1]

void generateArray(int a[], int n) {
    int i = -1;
    int r;
    bool alreadygot;

    while (i < n) {
        r = rand() % (10 * n); // make a random number in range 0..10n-1
        alreadygot = false;
        for (int j = 0; j <= i; j++)
            alreadygot = alreadygot || a[j] == r;

        if (!alreadygot) {
            i++;
            a[i] = r;
        }
    }
} // end of generateArray()

// Paste your working merge() function from part 1 here
//void merge(int a[], int f1, int l1, int f2, int l2) {
//    int work[l2+1]; // hardcode
//    int oneInd = 0, twoInd = 0, current = 0;
//
//    for(register int i=0; i<=l2; i++) // hardcode
//        work[i] = a[f1+i];
//
//    for(oneInd = f1, twoInd = f2, current = f1; (oneInd <= l1) && (twoInd <= l2);)
//    {
//        if(work[oneInd] < work[twoInd]) {
//            a[current] = work[oneInd];
//            //cout << work[oneInd] << ' ';
//            current++; oneInd++;
//        }
//        else if(work[twoInd] < work[oneInd]) {
//            a[current] = work[twoInd];
//            //cout << work[twoInd] << ' ';
//            current++; twoInd++;
//        }
//    }
//
//    // merge remaning items (one array will be done or all will be equal)
//    for(register int i=oneInd; i<=l1; i++) {
//        a[current] = work[oneInd];
//        current++; oneInd++;
//    }
//
//    for(register int i=twoInd; i<=l2; i++) {
//        a[current] = work[twoInd];
//        current++; twoInd++;
//    }
//
//} // end of merge()

void merge(int a[], int f1, int l1, int f2, int l2) {
    int work[ARRAYSIZE], i = f1, j = f2, k = 0;

    while(i <= l1 && j <= l2) {
        if(a[i] < a[j]) {
            work[k] = a[i];
            k++;
            i++;
        } else if(a[j] < a[i]) {
            work[k] = a[j];
            k++;
            j++;
        }
    }

    while(i <= l1) {
        work[k] = a[i];
        k++;
        i++;
    }
    while(j <= l2) {
        work[k] = a[j];
        k++;
        j++;
    }

    int y = 0;
    for(int h = f1; h <= l2; h++) {
        a[h] = work[y];
        y++;
    }

}

// mergesort a[first..last]
// Students have to write this function
void mergesort(int a[], int first, int last) {
    //cout << '\t' << first <<  ' ' << last << '\n';
    if(first < last) {
        int mid = (first + last) / 2;
        mergesort(a, first, mid);
        cout << "called 1 mergesort(" << first << ", " << mid << ")\n";
        mergesort(a, mid+1, last);
        cout << "called 2 mergesort(" << mid+1 << ", " << last << ")\n";
        merge(a, first, mid, mid+1, last);
    }

} // end of mergesort()

// a useful utility function to view the array
// prints out a[first..last]
void dumpArray(int a[], int first, int last) {
    for (int i = first; i <= last; i++)
        cout << a[i] << "  ";
    cout << endl;
}

Thanks for taking a look,

enduser000

[helios]

Windows is slightly more resilient to segmentation faults than Linux, for some reason.

generateArray(): Your while executes once too many. At the start of the last loop, i==n-1, then i++, and thus, a[n] = r;. Buffer overflow.