Question

I'm having trouble implementing the merge function on this recursive merge sort. I am not allowed to change the parameter list in the functions. This is what I have so far, written in C. So far I've been getting segfaults, and I feel like it's because I'm off by 1, somewhere...

void merge_the_array(int *list, int l1, int h1, int l2, int h2){

// create a temp array for l1-h1

int arr_a[(h1-l1)+1];

// create a temp array for l2-h2, adding 1 for the null

int arr_b[(h2-l2)+1];

// counting variables

int i = 0;

int j = 0;

int k = 0;

// begin merging the arrays

while((i <= h1) && (j <= h2)){

if(arr_a[i] <= arr_b[j]){

arr[k] = arr_a[i];

i++;

}

else{

arr[k] = arr_b[j];

j++;

}

k++;

}

// if a temp array runs out of elements, use the other

while(i <= h1){

arr[k] = arr_a[i];

i++;

k++;

}

while(j <= h2){

arr[k] = arr_b[j];

j++;

k++;

}

}

void merge_sort(int *arr, int low_index, int high_index){

if(low_index != high_index){

// adding 1, because high_index = n-1, low_index = 0, & midpoint = n/2

int mid = ((high_index - low_index)+1) / 2;

int l1 = low_index;

int l2 = mid+1;

int h1 = mid;

int h2 = high_index;

// call merge sort for low to mid

merge_sort(list, l1, h1);

//call merge sort for mid+1 to high

merge_sort(list, l2, h2);

// merge the two halves sorted

merge_the_array(list , l1, h1, l2, h2);

}

}

Answer 1

#include<iostream>
using namespace std;
void merge(int *arr,int start1,int start2,int end){

    int temp[1000000]; // creatting the temporary array for copying the elements
    int s1 = start1; // creatiing s1 variable
    int e1 = start2-1; // creatiing e1 variable
    int s2 = start2; // creatiing s2 variable
    int e2 = end; // creatiing e2 variable
    int k = 0;
    // beginning the merging function
    while(s1<=e1 && s2<=e2){
        if(arr[s1]<arr[s2]){
            temp[k++] = arr[s1++];
        }else{
            temp[k++] = arr[s2++];
        }
    }
    while(s1<=e1){
        temp[k++] = arr[s1++];
    }
    while(s2<=e2){
        temp[k++] = arr[s2++];
    }
    k = 0;
    for(int i=start1;i<=end;i++){
        arr[i] = temp[k++];
    }
    return;
}
void mergeSort(int * arr,int start,int end){
    if(start>=end){ // base condition
        return;
    }

    // start is the start index of the aaray
    // end is the last index of the array
    int mid = (start+end)/2; // mid points to the mid index of the aaray 

    mergeSort(arr,start,mid);// calling the merge sort for the 1st part of the array
     
    mergeSort(arr,mid+1,end);// calling the merge sort for the 2nd part of the array

    merge(arr,start,mid+1,end);// calling the merge function to merge 2 soted array
    return;
}
int main(){
    int arr[100] = {5,7,3,1,8,2};
    mergeSort(arr,0,5); // calling the merge sort function to sort the given array
    for(int i=0;i<6;i++){
        cout<<arr[i]<<endl;
    }
}