Why am I getting an incorrect o/p (0 4 0 0 0 0 0 0) for the below merge sort program?

I have written a program for merge sort here and passing the values in the program itself. The output that is being generated is mostly zeroes. Is it because of some error in the while loops or is it because my recursive logic is incorrect?

void merge(int arr[], int s, int e)
{
int mid = s + (e - s) / 2;
// the length of the two arrays that we are going to divide the main array in
int m = mid - s + 1;
int n = e - mid;
int* arr1 = new int[m];
int* arr2 = new int[n];
//copying values to arr1 and arr2 from the main array arr
int x = s;
for (int i = 0; i < m; i++) {
arr1[i] = arr[x + i];
}
for (int j = mid + 1; j < n; j++) {
arr2[j] = arr[mid + 1 + j];
}
int i = 0; // for arr1
int j = 0; // for arr2
int k = s; // because this is for the main array
while (i < m && j < n) {
if (arr1[i] <= arr2[j]) {
arr[k] = arr1[i];
i++;
k++;
}
else {
arr[k] = arr2[j];
k++;
j++;
}
while (i < m) {
arr[k] = arr1[i];
k++;
i++;
}
while (j < n) {
arr[k] = arr2[j];
k++;
j++;
}
}
delete[] arr1;
delete[] arr2;
}
//the recursive function
void divide(int arr[], int s, int e)
{
if (s >= e)
return;
int mid = s + (e - s) / 2;
divide(arr, s, mid);
divide(arr, mid + 1, e);
merge(arr, s, e);
}
#include <iostream>
using namespace std;
int main()
{
int n = 8;
int arr[8] = { 4, 8, 9, 7, 6, 2, 3, 1 };
divide(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}

Output for the above code that I am getting is ----> 0 4 0 0 0 0 0 0

You are getting seriously confused about your variables.

> int m = mid - s + 1;
> int n = e - mid;
>
> int* arr1 = new int[m];
> int* arr2 = new int[n];
>
> int x = s;
> for (int i = 0; i < m; i++) {
> arr1[i] = arr[x + i];
> }
> for (int j = mid + 1; j < n; j++) {
> arr2[j] = arr[mid + 1 + j];
> }

m is the midpoint, and an index into the full array. If is not the number of elements in the first part of the array. That would only be true if s equals zero.

So this is incorrect

> int* arr1 = new int[m];

it should be

int* arr1 = new int[m - s];

And this loop is incorrect

> int x = s;
> for (int i = 0; i < m; i++) {
> arr1[i] = arr[x + i];
> }

It should be

for (int i = s; i < m; i++) {
arr1[i - s] = arr[i];
}

etc. etc. I haven't pointed out all the mistakes but you get the idea. Think about what your variables mean, so that you use them correctly. It also wouldn't hurt to add some comments explaining what they mean, so you or anyone else doesn't get confused.

This for loop

for (int j = mid + 1; j < n; j++) {
arr2[j] = arr[mid + 1 + j];
}

is incorrect. Indices for the dynamically allocated array arr2 start from 0.

So you have to write

for (int j = 0; j < n; j++) {
arr2[j] = arr[mid + 1 + j];
}

And the second problem is incorrect using braces for the while loops

while (i < m && j < n) {
if (arr1[i] <= arr2[j]) {
arr[k] = arr1[i];
i++;
k++;
}
else {
arr[k] = arr2[j];
k++;
j++;
}
while (i < m) {
arr[k] = arr1[i];
k++;
i++;
}
while (j < n) {
arr[k] = arr2[j];
k++;
j++;
}
}

Instead there must be

while (i < m && j < n) {
if (arr1[i] <= arr2[j]) {
arr[k] = arr1[i];
i++;
k++;
}
else {
arr[k] = arr2[j];
k++;
j++;
}
}
while (i < m) {
arr[k] = arr1[i];
k++;
i++;
}
while (j < n) {
arr[k] = arr2[j];
k++;
j++;
}

That is the last two while loops shall be outside the first while loop.

And you may ignore the incorrect answer of @john that was upvoted even two times.:)