-5

Help me where I am wrong. Why I don't get a sorted array as my output.

#include<iostream>
using namespace std;

void mergalgo(int arr[], int start, int mid , int end){
    int resultant[5] {};
    int l=0;
    int k= mid+1;

    while(start<mid && k <end){
        if (arr[start]> arr[k]){
            resultant[l++] = arr[k++];
        }
        else{
            resultant[l++]= arr[start++];
        }
    }

    while(start<mid){
        resultant[l++]= arr[k++];
    }

    while(k<end){
        resultant[l++]= arr[k++];
    }

    for(int s=0; s<=end ;s++){
        arr[s]= resultant[s];
    }
}

void mergesort(int arr[], int start , int end){
    //base condition
    if(start<=end){
        return;
    }
    else{
        int mid= (start + end)/2;
        mergesort(arr, start, mid);
        mergesort(arr,mid+1,end);
        
        // merge algo
        mergalgo(arr, start, mid, end);
    }
}

int main(){
    int arr[5] {12,4,5,2,7};
    int start=0;
    int end=4;
    mergesort(arr,start,end);

    //sortd array
    for(int i= 0; i<=4; i++){
        cout<< arr[i]<< " "<< endl;
    }
}

Help me where i am wrong. I am new in C++ so plz do not try to use vectors plz use normal pointer so that i can understand it better.

And also help me on my test cases.. is it right or not because as i already told that .. I am new in programming so do not know that much clearly about all test cases..

paddy
  • 60,864
  • 6
  • 61
  • 103
Saksham Raj Singh
  • 1
  • 3
    Even if you don't want to use a debugger, you can make modifications to your program to test assumptions. Outputting values of variables is a good start. Your task is to ensure your implementation of the algorithm works the way you expect it to. Probing the program's behavior to find places where it's _not_ doing what you expect is called "debugging", and is an essential skill to practice. – paddy Jun 07 '23 at 03:18
  • 2
    Vectors are easier to parse than raw pointers. That's an odd request. – sweenish Jun 07 '23 at 03:18
  • 3
    a debugger knows how many items in a vector but not in a pointer so you have to specify it manually. Learn how to debug. It's a required skill going forward [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/995714) – phuclv Jun 07 '23 at 03:26
  • 1
    `if(start<=end){ return; }` Take a good look at that. This may help: https://godbolt.org/z/6d1vn38vx Once you figure that out you'll want to look at `while(start – Retired Ninja Jun 07 '23 at 03:34
  • Who is teaching you C++? The code looks like code written before 1998... the year that std::vector was introduced to replace "C" style arrays. If you can use C++20 consider [std::span](https://en.cppreference.com/w/cpp/container/span). – Pepijn Kramer Jun 07 '23 at 04:59
  • "I am new in C++ so plz do not try to use vectors plz use normal pointer so that i can understand it better." That is inconsistent, if you are new to C++ you should learn how to use vectors instead of C-like constructs. " I am new in programming so do not know that much clearly about all test cases." also is not clear to me. In fact I think what you mean by "I am new" is "My teacher wants ...". Which is fine (see https://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions ) but you should be more open about it. – Yunnosch Jun 07 '23 at 05:00
  • Good read: https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ – Yunnosch Jun 07 '23 at 05:00
  • 3
    I am new to "C++" this is an excellent reason to use std::vector. It is NOT advanced C++, it is basic C++. It will safe you from a lot of the headaches with "C" style arrays, specialy if you use the `.at(index)` method instead of the `[index]` operator. – Pepijn Kramer Jun 07 '23 at 05:06
  • Learn C++ from : [a recent C++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) or from [learncpp.com](https://www.learncpp.com/) that site is decent and pretty up to date. Then use [cppreference](https://en.cppreference.com/w/) for reference material (and examples). When you have done all that keep using [C++ core guidelines](https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines) to keep up to date with the latest best practices since C++ keeps evolving. – Pepijn Kramer Jun 07 '23 at 05:07
  • "I am new in C++ so plz do not try to use vectors..." thats a misunderstanding. Being new to c++ is not reason to not use `std::vector` but a reason to not use c-arrays. `std::vector` is the simple way. c-arrays are not for beginners. – 463035818_is_not_an_ai Jun 07 '23 at 07:08
  • https://www.youtube.com/watch?v=YnWhqhNdYyk – 463035818_is_not_an_ai Jun 07 '23 at 07:10

1 Answers1

1

Your code does not return a sorted array because of a logical mistake. The condition of the base case in the mergesort function is where the problem is.

You currently possess:

if (start <= end) {
    return;
}

To correctly identify the base case, this condition needs to be reversed to

if (start >= end)

Your code should now output the sorted array after this correction.

Gemunu R Wickremasinghe
  • 472
  • 4
  • 7