Merge sort not taking the last element

Question

#include<bits/stdc++.h>
using namespace std;
void mergel(int arr[], int low, int mid, int high){
    int i = low;
    int j = mid+1;
    int k = 0;
    int c[50];
    while(i<=mid && j<=high){
        if(arr[i]<arr[j]){
            c[k] = arr[i];
            i++;
            k++;
        }
        else{
            c[k] = arr[j];
            j++;
            k++;
        }
    }
    while(i<=mid){
        c[k] = arr[i];
        k++;
        i++;
    }
    while(j<=high){
        c[k] = arr[j];
        k++;
        j++;
    }
    for(i = low;i<k;i++){
        arr[i] = c[i];
    }
}
void mergesort(int arr[], int low, int high){
    if(low<high){
        int mid = low + (high-low)/2;
        mergesort(arr,low,mid);
        mergesort(arr,mid+1,high);
        mergel(arr,low,mid,high);
    }
}
int main(){
    int arr[] = {8,2,4,7,9,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    mergesort(arr,0,n-1);
       for(int i=0;i<n;i++){
        cout<<arr[i]<<endl;
    }
    return 0;

}

The sorted result is coming out to be {2,4,7,8,9,1}. The algorithms sorts every element in the unsorted array except the last element present in the array. Why is it happening? Please help.

I've been learning merge sort. I don't understand why this is happening. I've looked at various resources but even applying other solutions, the problem occurs again and again and I am unable to solve it. It would be a great help if the community helps me to solve the problem.

I know the problem is due to some simple bug on my code but I am unable to identify it on my own.

You want to read [this](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [this](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). — n. m. could be an AI, Oct 10 '22 at 08:00
Review the last `for` loop in your `mergel` function. The indices are wrong. — kotatsuyaki, Oct 10 '22 at 08:01
@kotatsuyaki how are the indices wrong. what should be the solution? — notaPROgrammer, Oct 10 '22 at 08:15

kotatsuyaki · Answer 1 · 2022-10-10T08:36:14.977

0

The indices used in the last for loop within the mergel function are wrong. Changing it from this

for(i = low; i < k; i++) {
    arr[i] = c[i];
}

to this

for (i = 0; i < k; i++) {
    arr[low + i] = c[i];
}

solves the problem.

Before the change, the loop copies the items from c[low...k-1] to arr[low...k-1] (notice that this is not even copying k elements), but the items should be copied from c[0...k-1] to arr[low...low+k-1].

edited Oct 10 '22 at 08:36

answered Oct 10 '22 at 08:24

kotatsuyaki

1,441
3
10
17

thankyou. but can you explain why this happened? – notaPROgrammer Oct 10 '22 at 08:28
@notaPROgrammer I've updated the answer to include some explanation. – kotatsuyaki Oct 10 '22 at 08:37

Merge sort not taking the last element

1 Answers1