What is wrong with this merge sort algorithm?

Question

Can someone please tell what is wrong with this piece of code? This code is to sort a set of elements in an array using merge sort.

#include<iostream>

void merge(int arr[], int left, int mid, int right){
    int left_ptr = left;
    int right_ptr = mid + 1;
    int size = right - left + 1;       
    int temp[size];
    int k = left;

    while (left_ptr <= mid && right_ptr <= right)
    {
        if(arr[left_ptr] <= arr[right_ptr]){
            temp[k] = arr[left_ptr];
            left_ptr++;
            k++;
        }
        else{
            temp[k] = arr[right_ptr];
            right_ptr++;
            k++;
        }
        
    }

    while (left_ptr <= mid)
    {
        temp[k] = arr[left_ptr];
        left_ptr++;
        k++;
    }

    while (right_ptr <= right)
    {
        temp[k] = arr[right_ptr];
        right_ptr++;
        k++;
    }
    
    for (int i = left_ptr; i < k; i++)
    {
        arr[i] = temp[i];
    }
    
}

void mergeSort(int arr[], int left, int right){
    int mid;
    if (left < right)
    {
        mid = (right + left)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    
}
int main(){
    int arr[] = {45,8,9,7,4,58,2,34,2,58}; 
    std::cout << arr << std::endl; 
    int size = sizeof(arr)/sizeof(int);
    mergeSort(arr, 0, size - 1);
    for (int i = 0; i < size; i++)
    {
        std::cout << arr[i] << "    ";
    }

    std::cout << std::endl;
    
}

I double checked it with many online codes and I see no error... What do you think went wrong? I tried to implement this using an array in-place (something like quick-sort).

Answer 1

Here is a list of things wrong with your code. I'm taking "wrong" broadly here. For each bit of code, my primary criticism is style based not "correctness", where the style aimed for is one that makes correctness easier to spot.

Along the way, one of the style criticisms results in spotting what looks like a bug.

void merge(int arr[], int left, int mid, int right){

1. You are using int to refer to offsets in an array.

2. You are using int[] parameters, which is a legacy C syntax for int* arr. Use something like std::span instead.

Going on:

 int left_ptr = left;

If your goal is to preserve the original arguments and work on copies, make the original arguments const so someone doesn't have to prove they aren't mutated in the body of the function.

int right_ptr = mid + 1;

You have variables called _ptr that aren't pointers.

int size = right - left + 1;

you appear to not be using half-open intervals. Use and learn to use half-open intervals. They are conventional in C++ and they really do get rid of lots of fence-post correcting code.

int temp[size];

This is not compliant C++. Practically, even on compilers that support this, many C++ implementations have much smaller stacks than the memory of arrays you might want to sort. This then results in your code blowing its stack.

Correctness is more important than performance. Creating dynamically sized objects on the stack leads to programs that engage in undefined behavior or crash on otherwise reasonable inputs.

int k = left;

this variable does not describe what it does.

while (left_ptr <= mid && right_ptr <= right)
while (left_ptr <= mid)
while (right_ptr <= right)

there is a lot of code duplication in these loops.

DRY - don't repeat yourself. Here, if there is a bug in any one of the repeats, if you DRY the bug would be in all uses and easier to spot. There are a lot of ways to DRY here (lambdas, helper functions, slightly more complex branching and one loop); use one of them.

for (int i = left_ptr; i < k; i++)
{
    arr[i] = temp[i];
}

looks like a manual std copy? Also looks like it has a bug, because of course manually reimplementing std copy means you did it wrong.

void mergeSort(int arr[], int left, int right){

again, legacy C-style array passing.

    int mid;

No need to declare this without initializing it. Move declarations as close as possible to their point of first use, and have them fall out of scope as soon as possible.

    if (left < right)
    {
        mid = (right + left)/2;

make this int mid =.

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

An example of how closed intervals make you have to do annoying fenceposting.

        merge(arr, left, mid, right);

mergeSort(arr, 0, size - 1);

another fencepost +/- 1 here.

Answer 2

I see two possible errors in the code:

Declaring int temp[size]; in merge is not valid, as size is not a constant. You will need to allocate the array dynamically.

Secondly, in the last segment of the merge function (the for loop), you initialize i = left_ptr. However, left_ptr is set equal to mid before that. I believe you actually want to initialize i = left.

EDIT: Just noticed: temp does not necessarily have to start at the beginning of arr. What I mean is, that each element of temp is mapped to a specific element of arr, but your code assumes at several plases, that temp[0] is mapped to arr[0], which is not true (temp[0] is actually mapped to arr[right]). There are two ways to fix that.

You can fix the pieces that are based on this assumption. Instead of arr[i] = temp[i], use arr[i + right] = temp[i] in the final for loop, and initialize k as zero.

Second option is to, instead of creating and deleting temp in every single call to merge, create it to be equal in size to arr and hold onto it for the entirety of execution of the algorithm (that could be done by creating it outside the algorithm and passing it to each call to merge or MergeSort) That way, the equal offset assumption would actually be correct.