-2

I have written this mergesort code but the output values are very weird. I have found out that the problem lies in code for mergee().

#include <iostream>

using namespace std;

void mergee(int arr[], int l, int mid, int r){
    int n1=(mid-l+1);
    int n2=(r-mid);
    int a[n1];
    int b[n2];
    for(int i=0;i<n1;i++){
        a[i]=arr[l+i];
    }
    for(int i=0;i<n2;i++){
        b[i]=arr[mid+1+i];
    }
    int i=0;
    int j=0;
    int k=1;
    while(i<n1 && j<n2){
        if(a[i]<b[j]){
            arr[k]=a[i];
            k++;
            i++;
        }
        else{
            arr[k]=b[j];
            k++;
            j++;
        }
    }
    while(i<n1){
        arr[k]=a[i];
        k++;
        i++;
    }
    while(j<n2){
        arr[k]=b[j];
        k++;
        j++;
    }
}

output: Enter number of elements: 5 Enter unsorted elements: 3 7 5 9 2 Sorted elements are: 3 3 2 7 2

I have no idea what is wrong. a couple of values are been outputed twice. been trying to debug for a hilw but to no avail.

Aryan Raveshia
  • 1
  • 2
  • Welcome back to Stack Overflow. Please re-read [ask] and *ask a question*. "I have no idea what is wrong" [is not answerable](https://meta.stackoverflow.com/questions/284236), and you should start by [trying to figure it out yourself first](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) - so that you can, at least, identify *what the actual problem is*, as opposed to just seeing the *symptoms*. – Karl Knechtel May 30 '22 at 11:06
  • 1
    I'd also create a [mcve], so you don't have to input the values manuall every time. Also, it's required here. – Ulrich Eckhardt May 30 '22 at 11:07
  • @KarlKnechtel agreed but i have tried to figure it out myself for a while. cannot solve it. hence the post – Aryan Raveshia May 30 '22 at 11:15
  • Have you tried running your code line by line in a debugger while monitoring the values of all variables, in order to determine in which line your program stops behaving as intended? If you did not try this, then you may want to read this: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/12149471) You may also want to read this: [How to debug small programs?](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) – Andreas Wenzel May 30 '22 at 11:46
  • Questions seeking debugging help should generally provide a [mre] of the problem, which includes a function `main` and all `#include` directives. This allows other people to easily test your program, by simply using copy&paste. I suggest that you create a function `main` with hard-coded sample input and call the function `mergee` with that sample input. Afterwards, it should print the result of the sort. Before posting such a function `main`, you should verify that it actually reproduces the problem. – Andreas Wenzel May 30 '22 at 11:49
  • `int a[n1];` is not C++ code but a compiler extension and will easily exhaust your stack. But allocating the arrays during sort will kill your performance. You should allocate a results array and pass it per reference through the recursions of the sort algorithm. The merge can then switch between using the original and result arrays copying the data back and forth. – Goswin von Brederlow May 30 '22 at 15:01
  • "but i have tried to figure it out myself for a while. cannot solve it." Okay, and while you were trying to figure it out, did you come to any conclusions about where the problem occurs, or why? *How* did you try to figure it out? – Karl Knechtel May 30 '22 at 16:01

1 Answers1

0

The error lies in your choice confusing variable names:

void mergee(int arr[], int l, int mid, int r){
    ...
    int k=1;

In many fonts the l and 1 look very similar and are easily confused. k should be initialized to l and not 1. If you had named the arguments left and right the error would be obvious.

Goswin von Brederlow
  • 11,875
  • 2
  • 24
  • 42