Mixing
how does this recursive function work? to merge sort two singly linked lists
I've found this recursive function in C++ on geeksforgeeks.org, to merge and sort two singly linked lists, I used netbeans to debug this code but still I can't get the clear idea behind the function of this code. also I've seen similar code stackoverflow but with no explanation about the way it works. my question is about the idea behind it and the way it works where the sufficient explanation here also will help others with the same question.
debugged the code on netbeans to understand the work flow of the code
//Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
Node *merge(Node *h1, Node *h2)
{
if (!h1)
return h2;
if (!h2)
return h1;
// start with the linked list
// whose head data is the least
if (h1->data < h2->data)
{
h1->next = merge(h1->next, h2);
return h1;
}
else
{
h2->next = merge(h1, h2->next);
return h2;
}
}
this function should return one sorted linked list
c++ function sorting recursion singly-linked-list
asked Jan 2 at 0:03
AnnunakiAnnunaki
102110
add a comment |
I've found this recursive function in C++ on geeksforgeeks.org, to merge and sort two singly linked lists, I used netbeans to debug this code but still I can't get the clear idea behind the function of this code. also I've seen similar code stackoverflow but with no explanation about the way it works. my question is about the idea behind it and the way it works where the sufficient explanation here also will help others with the same question.
debugged the code on netbeans to understand the work flow of the code
//Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
Node *merge(Node *h1, Node *h2)
{
if (!h1)
return h2;
if (!h2)
return h1;
// start with the linked list
// whose head data is the least
if (h1->data < h2->data)
{
h1->next = merge(h1->next, h2);
return h1;
}
else
{
h2->next = merge(h1, h2->next);
return h2;
}
}
this function should return one sorted linked list
c++ function sorting recursion singly-linked-list
asked Jan 2 at 0:03
AnnunakiAnnunaki
102110
3
Do some Google searching on "proof by induction". It's a mathematical concept, but it applies here perfectly. Once you've read and understood how proof by induction works, you should be able to understand this recursive function perfectly: presume that this function returns a sorted list. That's your starting point. This function returns a sorted list. You accept this fact, for granted. Now, go through this simple function, line by line, using the basic principles of proof by induction that you've just learned.
– Sam Varshavchik
Jan 2 at 0:06
linking Mathematical induction or Structural induction would've been helpful
– user633183
Jan 2 at 6:08
add a comment |
I've found this recursive function in C++ on geeksforgeeks.org, to merge and sort two singly linked lists, I used netbeans to debug this code but still I can't get the clear idea behind the function of this code. also I've seen similar code stackoverflow but with no explanation about the way it works. my question is about the idea behind it and the way it works where the sufficient explanation here also will help others with the same question.
debugged the code on netbeans to understand the work flow of the code
//Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
Node *merge(Node *h1, Node *h2)
{
if (!h1)
return h2;
if (!h2)
return h1;
// start with the linked list
// whose head data is the least
if (h1->data < h2->data)
{
h1->next = merge(h1->next, h2);
return h1;
}
else
{
h2->next = merge(h1, h2->next);
return h2;
}
}
this function should return one sorted linked list
c++ function sorting recursion singly-linked-list
asked Jan 2 at 0:03
AnnunakiAnnunaki
102110
I've found this recursive function in C++ on geeksforgeeks.org, to merge and sort two singly linked lists, I used netbeans to debug this code but still I can't get the clear idea behind the function of this code. also I've seen similar code stackoverflow but with no explanation about the way it works. my question is about the idea behind it and the way it works where the sufficient explanation here also will help others with the same question.
debugged the code on netbeans to understand the work flow of the code
//Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
Node *merge(Node *h1, Node *h2)
{
if (!h1)
return h2;
if (!h2)
return h1;
// start with the linked list
// whose head data is the least
if (h1->data < h2->data)
{
h1->next = merge(h1->next, h2);
return h1;
}
else
{
h2->next = merge(h1, h2->next);
return h2;
}
}
this function should return one sorted linked list
c++ function sorting recursion singly-linked-list
c++ function sorting recursion singly-linked-list
asked Jan 2 at 0:03
AnnunakiAnnunaki
102110
asked Jan 2 at 0:03
AnnunakiAnnunaki
102110
asked Jan 2 at 0:03
AnnunakiAnnunaki
102110
asked Jan 2 at 0:03
AnnunakiAnnunaki
102110
asked Jan 2 at 0:03
AnnunakiAnnunaki
102110
102110
3
Do some Google searching on "proof by induction". It's a mathematical concept, but it applies here perfectly. Once you've read and understood how proof by induction works, you should be able to understand this recursive function perfectly: presume that this function returns a sorted list. That's your starting point. This function returns a sorted list. You accept this fact, for granted. Now, go through this simple function, line by line, using the basic principles of proof by induction that you've just learned.
– Sam Varshavchik
Jan 2 at 0:06
linking Mathematical induction or Structural induction would've been helpful
– user633183
Jan 2 at 6:08
add a comment |
3
Do some Google searching on "proof by induction". It's a mathematical concept, but it applies here perfectly. Once you've read and understood how proof by induction works, you should be able to understand this recursive function perfectly: presume that this function returns a sorted list. That's your starting point. This function returns a sorted list. You accept this fact, for granted. Now, go through this simple function, line by line, using the basic principles of proof by induction that you've just learned.
– Sam Varshavchik
Jan 2 at 0:06
linking Mathematical induction or Structural induction would've been helpful
– user633183
Jan 2 at 6:08
3
3
Do some Google searching on "proof by induction". It's a mathematical concept, but it applies here perfectly. Once you've read and understood how proof by induction works, you should be able to understand this recursive function perfectly: presume that this function returns a sorted list. That's your starting point. This function returns a sorted list. You accept this fact, for granted. Now, go through this simple function, line by line, using the basic principles of proof by induction that you've just learned.
– Sam Varshavchik
Jan 2 at 0:06
Do some Google searching on "proof by induction". It's a mathematical concept, but it applies here perfectly. Once you've read and understood how proof by induction works, you should be able to understand this recursive function perfectly: presume that this function returns a sorted list. That's your starting point. This function returns a sorted list. You accept this fact, for granted. Now, go through this simple function, line by line, using the basic principles of proof by induction that you've just learned.
– Sam Varshavchik
Jan 2 at 0:06
linking Mathematical induction or Structural induction would've been helpful
– user633183
Jan 2 at 6:08
linking Mathematical induction or Structural induction would've been helpful
– user633183
Jan 2 at 6:08
add a comment |
2 Answers
2
active
oldest
votes
I added comments to the code. I also changed the if from < to <= in case this was being used for a merge sort, where if h1->data == h2->data, you'd want h1 first for stability. Keep in mind that the two lists are already sorted, this function is just merging them.
The function recursively follows the two lists, skipping past smaller nodes, until it reaches the end of one of the lists, at which point it sets the end of that list to the remainder of the other list and then returns back up the chain of recursive calls, working its way backwards along the lists, setting the smaller nodes next pointers to merge the lists from back to front. This is an inefficient way of merging lists, since it consumes O(n) stack space due to recursion on every node, but it's probably meant as a learning exercise, not to be efficient.
// initial input parameters, h1 and h2 each point to already sorted lists
Node *merge(Node *h1, Node *h2)
{
if (!h1) // if h1 empty
return h2; // return h2
if (!h2) // if h2 empty
return h1; // return h1
if (h1->data <= h2->data) // if h1->data <= h2->data
{
h1->next = merge(h1->next, h2); // h1->next = smaller of {h1->next, h2}
return h1; // return h1
}
else // else h1->data > h2->data
{
h2->next = merge(h1, h2->next); // h2->next = smaller of {h1, h2->next}
return h2; // return h2
}
}
answered Jan 2 at 1:17
rcgldrrcgldr
15.7k31435
add a comment |
I believe taking an example is the best way to understand how recursive algorithms work. Let's use these two sample linked lists as an example:
{13, 24, 74}{34, 72, 95}
Notice that both of them are sorted, since that's a requirement by the algorithm:
Given two sorted lists, merge them so as to produce a combined sorted list
I have compiled a trace of how this turns out:
- Arrow are execution order
- Each line is a stack frame. In particular, the line on the left is before recursive call for
merge, and the right is its result after.
Notice the following as well:
- On each arrow on the left, the smaller element from start of the nodes disappears
- on the way back, that smaller element gains sorted order of elements on the other side. On the very end we return the list that just gained the other one in a sorted form, namely: {13, 24, 34, 72, 74, 95}
answered Jan 2 at 4:37
aybassiounyaybassiouny
423212
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53999906%2fhow-does-this-recursive-function-work-to-merge-sort-two-singly-linked-lists%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
I added comments to the code. I also changed the if from < to <= in case this was being used for a merge sort, where if h1->data == h2->data, you'd want h1 first for stability. Keep in mind that the two lists are already sorted, this function is just merging them.
The function recursively follows the two lists, skipping past smaller nodes, until it reaches the end of one of the lists, at which point it sets the end of that list to the remainder of the other list and then returns back up the chain of recursive calls, working its way backwards along the lists, setting the smaller nodes next pointers to merge the lists from back to front. This is an inefficient way of merging lists, since it consumes O(n) stack space due to recursion on every node, but it's probably meant as a learning exercise, not to be efficient.
// initial input parameters, h1 and h2 each point to already sorted lists
Node *merge(Node *h1, Node *h2)
{
if (!h1) // if h1 empty
return h2; // return h2
if (!h2) // if h2 empty
return h1; // return h1
if (h1->data <= h2->data) // if h1->data <= h2->data
{
h1->next = merge(h1->next, h2); // h1->next = smaller of {h1->next, h2}
return h1; // return h1
}
else // else h1->data > h2->data
{
h2->next = merge(h1, h2->next); // h2->next = smaller of {h1, h2->next}
return h2; // return h2
}
}
answered Jan 2 at 1:17
rcgldrrcgldr
15.7k31435
add a comment |
I added comments to the code. I also changed the if from < to <= in case this was being used for a merge sort, where if h1->data == h2->data, you'd want h1 first for stability. Keep in mind that the two lists are already sorted, this function is just merging them.
The function recursively follows the two lists, skipping past smaller nodes, until it reaches the end of one of the lists, at which point it sets the end of that list to the remainder of the other list and then returns back up the chain of recursive calls, working its way backwards along the lists, setting the smaller nodes next pointers to merge the lists from back to front. This is an inefficient way of merging lists, since it consumes O(n) stack space due to recursion on every node, but it's probably meant as a learning exercise, not to be efficient.
// initial input parameters, h1 and h2 each point to already sorted lists
Node *merge(Node *h1, Node *h2)
{
if (!h1) // if h1 empty
return h2; // return h2
if (!h2) // if h2 empty
return h1; // return h1
if (h1->data <= h2->data) // if h1->data <= h2->data
{
h1->next = merge(h1->next, h2); // h1->next = smaller of {h1->next, h2}
return h1; // return h1
}
else // else h1->data > h2->data
{
h2->next = merge(h1, h2->next); // h2->next = smaller of {h1, h2->next}
return h2; // return h2
}
}
answered Jan 2 at 1:17
rcgldrrcgldr
15.7k31435
add a comment |
I added comments to the code. I also changed the if from < to <= in case this was being used for a merge sort, where if h1->data == h2->data, you'd want h1 first for stability. Keep in mind that the two lists are already sorted, this function is just merging them.
The function recursively follows the two lists, skipping past smaller nodes, until it reaches the end of one of the lists, at which point it sets the end of that list to the remainder of the other list and then returns back up the chain of recursive calls, working its way backwards along the lists, setting the smaller nodes next pointers to merge the lists from back to front. This is an inefficient way of merging lists, since it consumes O(n) stack space due to recursion on every node, but it's probably meant as a learning exercise, not to be efficient.
// initial input parameters, h1 and h2 each point to already sorted lists
Node *merge(Node *h1, Node *h2)
{
if (!h1) // if h1 empty
return h2; // return h2
if (!h2) // if h2 empty
return h1; // return h1
if (h1->data <= h2->data) // if h1->data <= h2->data
{
h1->next = merge(h1->next, h2); // h1->next = smaller of {h1->next, h2}
return h1; // return h1
}
else // else h1->data > h2->data
{
h2->next = merge(h1, h2->next); // h2->next = smaller of {h1, h2->next}
return h2; // return h2
}
}
answered Jan 2 at 1:17
rcgldrrcgldr
15.7k31435
I added comments to the code. I also changed the if from < to <= in case this was being used for a merge sort, where if h1->data == h2->data, you'd want h1 first for stability. Keep in mind that the two lists are already sorted, this function is just merging them.
The function recursively follows the two lists, skipping past smaller nodes, until it reaches the end of one of the lists, at which point it sets the end of that list to the remainder of the other list and then returns back up the chain of recursive calls, working its way backwards along the lists, setting the smaller nodes next pointers to merge the lists from back to front. This is an inefficient way of merging lists, since it consumes O(n) stack space due to recursion on every node, but it's probably meant as a learning exercise, not to be efficient.
// initial input parameters, h1 and h2 each point to already sorted lists
Node *merge(Node *h1, Node *h2)
{
if (!h1) // if h1 empty
return h2; // return h2
if (!h2) // if h2 empty
return h1; // return h1
if (h1->data <= h2->data) // if h1->data <= h2->data
{
h1->next = merge(h1->next, h2); // h1->next = smaller of {h1->next, h2}
return h1; // return h1
}
else // else h1->data > h2->data
{
h2->next = merge(h1, h2->next); // h2->next = smaller of {h1, h2->next}
return h2; // return h2
}
}
answered Jan 2 at 1:17
rcgldrrcgldr
15.7k31435
edited Jan 2 at 4:18
answered Jan 2 at 1:17
rcgldrrcgldr
15.7k31435
answered Jan 2 at 1:17
rcgldrrcgldr
15.7k31435
answered Jan 2 at 1:17
rcgldrrcgldr
15.7k31435
15.7k31435
add a comment |
add a comment |
I believe taking an example is the best way to understand how recursive algorithms work. Let's use these two sample linked lists as an example:
{13, 24, 74}{34, 72, 95}
Notice that both of them are sorted, since that's a requirement by the algorithm:
Given two sorted lists, merge them so as to produce a combined sorted list
I have compiled a trace of how this turns out:
- Arrow are execution order
- Each line is a stack frame. In particular, the line on the left is before recursive call for
merge, and the right is its result after.
Notice the following as well:
- On each arrow on the left, the smaller element from start of the nodes disappears
- on the way back, that smaller element gains sorted order of elements on the other side. On the very end we return the list that just gained the other one in a sorted form, namely: {13, 24, 34, 72, 74, 95}
answered Jan 2 at 4:37
aybassiounyaybassiouny
423212
add a comment |
I believe taking an example is the best way to understand how recursive algorithms work. Let's use these two sample linked lists as an example:
{13, 24, 74}{34, 72, 95}
Notice that both of them are sorted, since that's a requirement by the algorithm:
Given two sorted lists, merge them so as to produce a combined sorted list
I have compiled a trace of how this turns out:
- Arrow are execution order
- Each line is a stack frame. In particular, the line on the left is before recursive call for
merge, and the right is its result after.
Notice the following as well:
- On each arrow on the left, the smaller element from start of the nodes disappears
- on the way back, that smaller element gains sorted order of elements on the other side. On the very end we return the list that just gained the other one in a sorted form, namely: {13, 24, 34, 72, 74, 95}
answered Jan 2 at 4:37
aybassiounyaybassiouny
423212
add a comment |
I believe taking an example is the best way to understand how recursive algorithms work. Let's use these two sample linked lists as an example:
{13, 24, 74}{34, 72, 95}
Notice that both of them are sorted, since that's a requirement by the algorithm:
Given two sorted lists, merge them so as to produce a combined sorted list
I have compiled a trace of how this turns out:
- Arrow are execution order
- Each line is a stack frame. In particular, the line on the left is before recursive call for
merge, and the right is its result after.
Notice the following as well:
- On each arrow on the left, the smaller element from start of the nodes disappears
- on the way back, that smaller element gains sorted order of elements on the other side. On the very end we return the list that just gained the other one in a sorted form, namely: {13, 24, 34, 72, 74, 95}
answered Jan 2 at 4:37
aybassiounyaybassiouny
423212
I believe taking an example is the best way to understand how recursive algorithms work. Let's use these two sample linked lists as an example:
{13, 24, 74}{34, 72, 95}
Notice that both of them are sorted, since that's a requirement by the algorithm:
Given two sorted lists, merge them so as to produce a combined sorted list
I have compiled a trace of how this turns out:
- Arrow are execution order
- Each line is a stack frame. In particular, the line on the left is before recursive call for
merge, and the right is its result after.
Notice the following as well:
- On each arrow on the left, the smaller element from start of the nodes disappears
- on the way back, that smaller element gains sorted order of elements on the other side. On the very end we return the list that just gained the other one in a sorted form, namely: {13, 24, 34, 72, 74, 95}
answered Jan 2 at 4:37
aybassiounyaybassiouny
423212
answered Jan 2 at 4:37
aybassiounyaybassiouny
423212
answered Jan 2 at 4:37
aybassiounyaybassiouny
423212
answered Jan 2 at 4:37
aybassiounyaybassiouny
423212
423212
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53999906%2fhow-does-this-recursive-function-work-to-merge-sort-two-singly-linked-lists%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
Do some Google searching on "proof by induction". It's a mathematical concept, but it applies here perfectly. Once you've read and understood how proof by induction works, you should be able to understand this recursive function perfectly: presume that this function returns a sorted list. That's your starting point. This function returns a sorted list. You accept this fact, for granted. Now, go through this simple function, line by line, using the basic principles of proof by induction that you've just learned.
– Sam Varshavchik
Jan 2 at 0:06
linking Mathematical induction or Structural induction would've been helpful
– user633183
Jan 2 at 6:08