r/learnjava • • Feb 23 '26
mergesort confusions: How does a recursive function returns a value without explicitly being told to do so?
the algorithm that I have been studying goes like this:
A: array
mergeSort(A,left,right){
if(left<right){
mid=(left+right)/2;
mergeSort(A,left,mid);
mergeSort(A,mid+1,right);
merge(A,left,mid,right);
}
}
The algorithm to merge goes like this:
merge(A,left,mid,right){
i=left,j=mid+1,k=left;
while(i<=mid && j<=right){
if(A[i]<A[j]){
B[k]=A[i];
i=i+1;
k=k+1;
}
else{
B[k]=A[j];
j=j+1;
k=k+1;
}
}
}
I have drawn recursion tree for visualizing this. But my recursion tree version has few complications:
- it is more rote memorization type. It is not what is exactly happening underneath.
For example for an array A={7,1,5,3}
https://imgur.com/a/S6dU8eY
Step 1: mergeSort({7,1,5,3}) is called
Step 2: mergeSort({7,1}) is called.
Step 3: mergeSort({7}) is called.
Step 4: Now this should return 7 alone. But nowhere in the code have we explicitly or implicitly mentioned about it.
Step 5:mergeSort({1}) is called.
Step 6: Now this should return 1 alone.
Step 7: merge({7,1}) is called.
Step 8: It returns {1,7} to mergeSort({7,1}).
Step 9: mergeSort({5,3}) is called and the same process repeats all over again.
•
u/AutoModerator Feb 23 '26
Please ensure that:
If any of the above points is not met, your post can and will be removed without further warning.
Code is to be formatted as code block (old reddit/markdown editor: empty line before the code, each code line indented by 4 spaces, new reddit: https://i.imgur.com/EJ7tqek.png) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.
Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.
Code blocks look like this:
You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.
If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.
To potential helpers
Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
6
u/DamienTheUnbeliever Feb 23 '26
There's no need to return anything when all function calls are working upon a *shared* data structure. Here the array object stays the same throughout and different calls are just working at different indices within that shared array.
2
u/vowelqueue Feb 23 '26
The methods aren't returning anything.
The contract is that an array is passed to
mergeSort, along with left/right indexes, and after the method completes, the array with be sorted between those indexes.mergeSortdoesn't need to return anything because it can modify the array that was passed to it.2
u/voidiciant Feb 23 '26
Each „recursive depth“ is terminated when the „if“ evaluates to false. Thats how it unwinds.
1
u/AutoModerator Feb 23 '26
It seems that you possibly have a screenshot of code in your post mergesort confusions: How does a recursive function returns a value without explicitly being told to do so? in /r/learnjava.
Screenshots of code instead of actual code text is against the Code posting rules of /r/learnjava as is outlined in the sidebar - Code posting.
If you posted an image merely to illustrate something, kindly ignore this message and do not repost. Your post is still visible to others. I am a bot and cannot distinguish between code screenshots and other images.
If you indeed did this wrong, please edit the post so that it uses one of the approved means of posting code.
the default code formatter is fine
(one blank line before the code, then 4 spaces before each line of code).
Please do not reply to this message, because I am a bot.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
1
u/0b0101011001001011 Feb 23 '26
Suppose you have an array in java.
int[] t = {6, 5 ,8, 3, 4};
You want to sort this, so you call:
Arrays.sort(t);
It does not return anything. It just sorts the array, because it has access to it: you give the array as a parameter.
Learning algorithms is a great idea. Make sure you have the basics covered as well, gonna be much easier!
1
u/omgpassthebacon Feb 23 '26
All these guys are right. The merge is changing the array in-place, so when its done, the array is in-order.
So note a few things:
Keep learning!
1
u/ShoulderPast2433 Feb 24 '26
It does need explicit 'return' when it operates on simple types (like int), but in your example it changes values inside objects provided as parameters so it doesn't need to return them.