1

Im working on implementing sort algorithms for class and mergesort is the only one that has stumped me. Ive run into seg faults and other issues but once I've "solved" those im now stuck with the array giving duplicate values, memory addresses, and not sorted. Code below:

void merge(int* array, int first, int mid, int last){
    int first1 = first;
    int tempArr[last + 1];
    int first2 = mid + 1; 
    int last1 = mid; 
    int last2 = last;
    int index = first1; 

    for(; (first1 <= last1) && (first2 <= last2); ++index){
        if(array[first1] < array[first2]){
            tempArr[index] = array[first1];
            ++first1;
        }else {
            tempArr[index] = array[first2];
            ++first2;
        }
    }

    for(; first1 <= last1; ++first1, ++index){
        tempArr[index] = array[first1];
    }
    
    for(; first2 <= last2; ++first2, ++index){
        tempArr[index] = array[first2];
    }

//assigns sorted values to original array
    for(index = 0; index <= last; ++index){
        array[index] = tempArr[index];
    }
}


void mergeSort(int *array, int first, int last){
    int mid = (first + last) / 2;
    if (first < last){
        mergeSort(array, first, mid);
        mergeSort(array, mid+1, last);

        merge(array, first, mid, last);
    }
}

input :

array[] = {99, 23, 87, 67, 34, 12, 9, 44, 67, 73, 21, 71, 65, 48, 22, 89, 5, 11, 55, 31, 61, 29, 19, 49, 51};

output :

19 23 22 22 49 51 51 61 23 22 61 23 22 18894848128 32767 23 1889484128 32767 23 19 23 22 49 51

Any help is appreciated! p.s. this is my first time posting so sorry for any errors in formatting.

Royland2.0
  • 21
  • 4
  • Word of advice. Refactor your code to use half-open intervals. It makes everything much much more simple. https://stackoverflow.com/questions/13066884/what-is-half-open-range-and-off-the-end-value – Jeffrey Jan 25 '22 at 02:20
  • 1
    Two things jump out at me. First the way you’re declaring the temp array isn’t standard. Second, just from looking at the code it doesn’t look like you guarantee you start at index 0 for the data in temp array, but you always start coping out of it at zero. I’d write tests for functions. Thinking about edge cases and weird inputs. Best way to debug your code. – Taekahn Jan 25 '22 at 03:13
  • The variable sized array is an extension of g++ (a holdover from C). It's non-standard in C++, but it's not the end of the world if people make use of it. – selbie Jan 25 '22 at 03:41

0 Answers0