Cannot implement merge sort in C++

Question

I'm new to algorithms, I've been trying to get the merge sort work, but it just won't give the right output. No compilation errors, but I guess it's just flawed somewhere, showing random values in output as the sorted array.

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

int main() {
    int Arr[100], num_of_elements;
    cout << "Enter the number of elements (max 100): ";
    cin >> num_of_elements;
    cout << "Enter array elements: \n";
    for (int i = 0;i < num_of_elements;++i)
        cin >> Arr[i];
    merge_sort(Arr, 0, num_of_elements - 1);
    cout << "\nAfter Sorting (by Merge Sort):\n";
    printarray(Arr, num_of_elements);
    cout << endl;
    return 0;
}

void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }  
}

void merge(int arr[], int left, int mid, int right) {
    int i, j, k;

    /* Calculate the lengths of the subarrays and copy the elements into them */
    int lenght_left = mid - left + 1;
    int length_right = right - mid;
    int *leftarray = new int[lenght_left];
    int *rightarray = new int[length_right];
    for (i = 0;i < lenght_left;++i)
        leftarray[i] = arr[left + i];
    for (j = 0;j < length_right;++j)
        rightarray[j] = arr[mid + 1 + j];

    /* Reordering the elements in the original array */
    for (k = left, i = 0, j = 0;k <= right;++k) {
        if (leftarray[i] <= rightarray[j])
            arr[k] = leftarray[i++];
        else
            arr[k] = rightarray[j++];
    }  

    /* Copy remaining elements into the array */
    while (i < lenght_left)
        arr[k] = leftarray[i++];
    while (j < length_right)
        arr[k] = rightarray[j++];
    delete[](leftarray);
    delete[](rightarray);
}

void printarray(int arr[], int num) {
    cout << "Displaying Elements in array: \n";
    for (int i = 0;i < num;i++)
        cout << arr[i] << "  ";
}

Answer 1

In your merge function:

/* Reordering the elements in the original array */
for (k = left, i = 0, j = 0; k <= right; ++k) {
//                           ^^^^^^^^^^^
// It should be i < lenght_left && j < length_right
    if (leftarray[i] <= rightarray[j])
        arr[k] = leftarray[i++];
    else
        arr[k] = rightarray[j++];
}

The condition you're using to control the loop is not right, the condition should be with respect to your leftarray and rightarray, it should be, that when either of the arrays reach to their end, so change your condition to i < lenght_left && j < length_right.

And when copying the remaining elements in the same function:

/* Copy remaining elements into the array */
while (i < lenght_left)
    arr[k] = leftarray[i++];
//     ^^^
while (j < length_right)
    arr[k] = rightarray[j++];
//     ^^^

Here, you forgot to increment k, change them to k++.

Answer 2

There are couple of mistakes you are making:

1. You need to check that you don't go over the length of the array when you're merging

   Namely instead of:

   for (k = left, i = 0, j = 0;k <= right;++k)
   

   You should have:

   for (k = left, i = 0, j = 0;k <= right && i <lenght_left && j<length_right;++k)
   

2. You forget to increase the array counter when adding the leftover elements. Namely:

   while (i < lenght_left)
       arr[k] = leftarray[i++];
   while (j < length_right)
       arr[k] = rightarray[j++];
   

   You should have:

   while (i < lenght_left)
       arr[k++] = leftarray[i++];
   while (j < length_right)
       arr[k++] = rightarray[j++];