#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.

CodePudding user response：

You can use std::sort(arr, arr n) to sort any unsorted array with size n.

CodePudding user response：

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].