Stack Smashing Mergesort Help

[abstract mural]

Hey there, I've been trying to come up with a mergesort implementation, but I've been getting weird errors that I don't know how to fix. Can someone help out?

[versed agate]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question use !howto ask.

[abstract mural]

https://paste.rs/mkf4G.c%2B%2B (here is the code)

I've been trying to debug it:

I tried using backtrace but I got no useful information from it

[abstract mural]

I think it might have to do with the arrays left_split and right_split, but I'm not sure

[gritty igloo]

It's been a little while since I've done merge sort in algorithms class, but I'll take a shot at this. I noticed that the split arrays are one short: they are missing values to mark their ends. This is so that the merge loop can stop upon finding the end values. In the pseudocode, Infinity is used to mark endings but something like a max 32 bit integer constant could do.

The same pseudocode as my old lecture notes:
https://external-content.duckduckgo.com/iu/?u=https%3A%2F%2Fi.stack.imgur.com%2F7bUCK.png&f=1&nofb=1&ipt=67c5fe275bc189b33bd75d9f11f1adc32dcd29401bf3e3d2effdfd9287b8ac76&ipo=images

(Also consider how the pseudocode uses indexing from 1)

[abstract mural]

I'm pretty sure that code is equivalent to mine, the while loops at the bottom here should have the same effect as the infinity value:

The infinities just allow us to "push" any remaining values after either left or right becomes empty, which the while loops are doing too

@gritty igloo looked online at other implementations and some people are using new for the temp left and right array

Do you think that would have to do with it?

right now when I run it I get something like tihs:

[gritty igloo]

Hmm, I remember implementing mergesort with dynamically allocating the left and right subarrays. For the pseudocode above, I followed it almost exactly.

As for debugging, I noticed some strange negative values. Perhaps some garbage memory is being accessed?

[lunar mural]

You're going out of bounds when you start merging the right half. It looks like you copied the code from the left half and didn't change the variables

[abstract mural]

Ohhh

Let me check on that

@lunar mural yeah that fixed it thank you so much!

[abstract mural]

Why would we have to dynamically allocate left and right ? I remember seeing that too and not knowing why.

[versed agate]

Thank you and let us know if you have any more questions!

This thread is now set to auto-hide after an hour of inactivity

[gritty igloo]

For my implementation, I coded it to accept arbitrarily generated arrays if I recall correctly. Numbers were random in a range, etc. So I decided to use dynamic allocation for subarrays since I didn't feel certain about exactly how much memory I really need at the time.

[abstract mural]

Got it, thanks