Merge Sort - Segmentation Error

I've been programming in Python for more than a year now, and I just moved back to C++, to learn a few basic algorithms. I started with merge sort, but it gives me a segmentation errror. Help would be greatly appreciated. I think I debugged where it happens, but I'm unable to understand why.

#include <iostream>
using namespace std;
void* merge(int array1[], int array2[], int low, int mid, int high){
    int i, j, k;
    for (i = low,j = mid, k = low; i < mid, j < high; k++){
        if (array1[i] < array1[j]){
            array2[k] = array1[i];
            i++;
            }
        else{
            array2[k] = array1[j];
            j++;
        }
    }
    if (i == mid){
        for (; j < high; j++, k++){
            array2[k] = array1[j];
            }
    }
else{
    for (; i < mid; i++, k++){
        array2[k] = array1[i];
    }
}
void* merge_sort(int array1[], int copy[], int low, int high){
    int mid;
    int range = high - low;
    if (range == 1)
        copy[low] = array1[low];
    else{
        mid = low + range/2;
        merge_sort(array1, copy, low, mid);
        // Segmentation error seems to be here.
        merge_sort(array1, copy, mid, high);
     }
     merge(array1, copy, low, mid, high);
}

int main()
{
    int n, temp;
    cout << "How many numbers do you want to enter?" << endl;
    cin >> n;
    int numarray[n];
    for (int i = 0; i < n; i++){
        cin >> numarray[i];
    }
    int dumarray[n];  // Used for filling elements from merge sort
    merge_sort(numarray, dumarray, 0, n);
    cout << "Merge Sort" << endl;
    for (int i = 0; i < n; i++){
        cout << dumarray[i] << endl;
    } 
    return 0;
}

EDIT:

#include <iostream>
using namespace std;

void merge_sort(int [], int [], int, int);

void merge(int array1[], int array2[], int low, int mid, int high){
    int i, j, k;
    for (i = low,j = mid, k = low; i < mid, j < high; k++){
        if (array1[i] < array1[j]){
            array2[k] = array1[i];
            i++;
            }
        else{
            array2[k] = array1[j];
            j++;
        }
    }
    if (i == mid){
        for (; j < high; j++, k++){
            array2[k] = array1[j];
            }
    }
    else{
        for (; i < mid; i++, k++){
            array2[k] = array1[i];
            }
    }
}

void merge_sort(int array1[], int copy[], int low, int high){
    int mid;
    int range = high - low;
    mid = low + range/2;
    if (range == 1)
        copy[low] = array1[low];
    else{
        mid = low + range/2;
        merge_sort(array1, copy, low, mid);
        merge_sort(array1, copy, mid, high);
    merge(array1, copy, low, mid, high);
    }
}
int main(){
    int n, temp;
cout << "How many numbers do you want to enter?" << endl;
cin >> n;
int numarray[n];
for (int i = 0; i < n; i++){
    cin >> numarray[i];
}
    int dumarray[n];
    merge_sort(numarray, dumarray ,0, n);
    for (int i = 0; i < n; i++){
        cout << dumarray[i] << endl;
    }

}

Answers


The calculation for mid value seems to be wrong. Try calculating mid as

mid = low + (high-low)/2

Edit: Move merge(array1, copy, low, mid, high);inside the else bracket.

else
{
    mid = low + range/2;
    merge_sort(array1, copy, low, mid);
    merge_sort(array1, copy, mid, high);
    merge(array1, copy, low, mid, high);
}

The merge function also has a lot of bugs. The condition check in the initial for loop i < mid, j < high is separated by a comma which means it is only checking for j < high and discarding condition check for i.


Need Your Help

Eclipse (ZIP distro) SWT link error

java eclipse ubuntu unsatisfiedlinkerror

Eclipse seems to be unable to start an embedded browser.

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.