Can't find error in my merge sort implementation, getting wrong output?

Question

In the code below I was given unsorted array had to find kth smallest Given an array arr[] and an integer K where K is smaller than size of array, the task is to find the Kth smallest element in the given array. It is given that all array elements are distinct.


#include<bits/stdc++.h>
using namespace std;

Merge function:


void merge(int arr[],int l,int m,int r){
    int marr[(r-l)+1];
    int i=l,j=m+1,k=0;
    for(k;k<=(r-l);k++){
        if(i==(m+1)){
            marr[k]=arr[j];
            j++;
        }
        else if(j==(r+1)){
            marr[k]=arr[i];
            i++;
        }
        else if(arr[i]<=arr[j]){
            marr[k]=arr[i];
            i++;
        }
        else if(arr[i]>arr[j]){
            marr[k]=arr[j];
            j++;
        }
    }
    //Below assignment was creating wrong output but cant figure out why?
    for(k=0;k<=(r-l);k++,l++){
         arr[l]=marr[k];
     }
//However below code worked instead, in spite tracing same no. of values
//for(int x=l,k=0;x<=r;x++,k++){
        
      //  arr[x]=marr[k];
//}

Mergesort:

void mergesort(int arr[], int l,int r){
    if(r<=l)
    return;
    int mid=l+(r-l)/2;
    mergesort(arr,l,mid);
    mergesort(arr,mid+1,r);
    merge(arr,l,mid,r);
} 

class Solution{
    public:
    // arr : given array
    // l : starting index of the array i.e 0
    // r : ending index of the array i.e size-1
    // k : find kth smallest element and return using this function
    int kthSmallest(int arr[], int l, int r, int k) {
    
        mergesort(arr,l,r);
   
        return arr[k-1];
        
        

    }
};

Driver Code starts

int main()
{
    int test_case;
    cin>>test_case;
    while(test_case--)
    {
        int number_of_elements;
        cin>>number_of_elements;
        int a[number_of_elements];
        
        for(int i=0;i<number_of_elements;i++)
            cin>>a[i];
            
        int k;
        cin>>k;
        Solution ob;
        cout<<ob.kthSmallest(a, 0, number_of_elements-1, k)<<endl;
    }
    return 0;
}

Driver Code ends

`int marr[(r-l)+1];` -- This is not C++ code, and then: `using namespace std;` -- This is not `C` code. Choose a language, either C++ or C, not both. — PaulMcKenzie, Feb 09 '22 at 09:41
@RajGupta I suggest to stop using dodgy websites as a learning tool in writing readable and proper C++. Read why using the bits header [should not be done](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). Second, variable length arrays are [not standard C++](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). — PaulMcKenzie, Feb 09 '22 at 09:44
l=left most index of array; m=mid ; j=m+1; Also this code runs in C++ but gives wrong output. — Raj Gupta, Feb 09 '22 at 09:46
As to the C++ solution to your problem, [std::nth_element](https://en.cppreference.com/w/cpp/algorithm/nth_element) gives you the answer immediately. — PaulMcKenzie, Feb 09 '22 at 09:46
@RajGuptaInstead of explaining "l=left most index of array" etc, rename the variables accordingly, e.g. `l` to `leftIndex` or similar. — Bodo, Feb 09 '22 at 09:55
@RajGupta Change this: `int a[number_of_elements];` --> to this: `std::vector a(number_of_elements);`. Dynamic arrays in C++ are accomplished by using `std::vector`. — PaulMcKenzie, Feb 09 '22 at 10:04

score 1 · Accepted Answer · answered Feb 09 '22 at 10:12

The non-standard variable length arrays and other considerations notwithstanding (seriously, get a good reference book and reputable tutorial guide), the problem is in your merge algorithm:

At the end of merge you're trying to put the sorted marr data back into arr. That is done here:

for(k=0;k<=(r-l);k++,l++)
{
    arr[l]=marr[k];
}

The problem is the increment of l, which has the effect of shortening the merge because it causes (r-l) to collapse toward k, while k is ascending upward. This means you don't copy all your data, and you're left not-only with partial sorting, you're left with potential duplicate junk in arr (in fact, it is highly likely).

Replacing that with this:

for (i=0; i<=(r-l); ++i)
{
    arr[i+l] = marr[i];
}

should fix it for you. This runs i from 0..segment length inclusive, drops the results into the adjusted offset i+l location.

Everything either wrong or poor in this code has been deftly mentioned in comments, so I'll leave that for you to address (and believe me, you want to address all of it).

Can't find error in my merge sort implementation, getting wrong output?

1 Answers1