Mixing
I have written mergesort 2 different ways, is the space complexity better in one of them over the other?
I have been practicing algorithms and data structures lately and got to this part https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html on mergesort of an online book. The book gives an implementation for the algorithm and I tried rewriting it so it used less space, here is my code (please refer to the link for the book's code):
def mergeSort(alist, l, r):
if r - l >= 1:
mid = (r + l)//2
mergeSort(alist, l, mid)
mergeSort(alist, mid+1, r)
i = l
j = mid+1
k = l
temp_list = alist[:]
while i < mid+1 and j < r+1:
if temp_list[i] <= temp_list[j]:
alist[k] = temp_list[i]
i=i+1
else:
alist[k] = temp_list[j]
j=j+1
k=k+1
while i < mid+1:
alist[k] = temp_list[i]
i=i+1
k=k+1
while j < r+1:
alist[k] = temp_list[j]
j=j+1
k=k+1
From what I have been reading online the space complexities of my version and the one you can find at this link https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html are O(n). If you do it the way it is done in the link it is easy to make the mistake of assuming space complexity is O(nlogn) but since all the stack frames are not "alive" together it is actually O(n) right ?
My version only creates an additional list of size n every time we are merging so I don't have extra space used on the stack for storing the left and right sublists.
So my questions are:
a) Even though both versions use O(n) space, does mine actually use less space than the one in the book by some constant factor or something ?
b) How about time complexity ? I don't think it has changed... but I am new to this stuff so maybe I screwed it up.
Thanks,
d_darric
python mergesort space-complexity
asked Jan 1 at 15:16
d_darricd_darric
388
add a comment |
I have been practicing algorithms and data structures lately and got to this part https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html on mergesort of an online book. The book gives an implementation for the algorithm and I tried rewriting it so it used less space, here is my code (please refer to the link for the book's code):
def mergeSort(alist, l, r):
if r - l >= 1:
mid = (r + l)//2
mergeSort(alist, l, mid)
mergeSort(alist, mid+1, r)
i = l
j = mid+1
k = l
temp_list = alist[:]
while i < mid+1 and j < r+1:
if temp_list[i] <= temp_list[j]:
alist[k] = temp_list[i]
i=i+1
else:
alist[k] = temp_list[j]
j=j+1
k=k+1
while i < mid+1:
alist[k] = temp_list[i]
i=i+1
k=k+1
while j < r+1:
alist[k] = temp_list[j]
j=j+1
k=k+1
From what I have been reading online the space complexities of my version and the one you can find at this link https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html are O(n). If you do it the way it is done in the link it is easy to make the mistake of assuming space complexity is O(nlogn) but since all the stack frames are not "alive" together it is actually O(n) right ?
My version only creates an additional list of size n every time we are merging so I don't have extra space used on the stack for storing the left and right sublists.
So my questions are:
a) Even though both versions use O(n) space, does mine actually use less space than the one in the book by some constant factor or something ?
b) How about time complexity ? I don't think it has changed... but I am new to this stuff so maybe I screwed it up.
Thanks,
d_darric
python mergesort space-complexity
asked Jan 1 at 15:16
d_darricd_darric
388
Ok but at any point in time I only have one copy of the full list since I only do the merging on the “way up” in the recursion. And as soon as the merge operation is done the stack frame is “killed”. Basically I never have two copies of my list alive at the same time. Which is why I think I am still inO(n)space. Can you tell me where specifically is my reasoning false ?
– d_darric
Jan 1 at 16:03
Please refer to this link <stackoverflow.com/questions/54004903/…> for the answer.
– d_darric
Jan 2 at 19:58
add a comment |
I have been practicing algorithms and data structures lately and got to this part https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html on mergesort of an online book. The book gives an implementation for the algorithm and I tried rewriting it so it used less space, here is my code (please refer to the link for the book's code):
def mergeSort(alist, l, r):
if r - l >= 1:
mid = (r + l)//2
mergeSort(alist, l, mid)
mergeSort(alist, mid+1, r)
i = l
j = mid+1
k = l
temp_list = alist[:]
while i < mid+1 and j < r+1:
if temp_list[i] <= temp_list[j]:
alist[k] = temp_list[i]
i=i+1
else:
alist[k] = temp_list[j]
j=j+1
k=k+1
while i < mid+1:
alist[k] = temp_list[i]
i=i+1
k=k+1
while j < r+1:
alist[k] = temp_list[j]
j=j+1
k=k+1
From what I have been reading online the space complexities of my version and the one you can find at this link https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html are O(n). If you do it the way it is done in the link it is easy to make the mistake of assuming space complexity is O(nlogn) but since all the stack frames are not "alive" together it is actually O(n) right ?
My version only creates an additional list of size n every time we are merging so I don't have extra space used on the stack for storing the left and right sublists.
So my questions are:
a) Even though both versions use O(n) space, does mine actually use less space than the one in the book by some constant factor or something ?
b) How about time complexity ? I don't think it has changed... but I am new to this stuff so maybe I screwed it up.
Thanks,
d_darric
python mergesort space-complexity
asked Jan 1 at 15:16
d_darricd_darric
388
I have been practicing algorithms and data structures lately and got to this part https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html on mergesort of an online book. The book gives an implementation for the algorithm and I tried rewriting it so it used less space, here is my code (please refer to the link for the book's code):
def mergeSort(alist, l, r):
if r - l >= 1:
mid = (r + l)//2
mergeSort(alist, l, mid)
mergeSort(alist, mid+1, r)
i = l
j = mid+1
k = l
temp_list = alist[:]
while i < mid+1 and j < r+1:
if temp_list[i] <= temp_list[j]:
alist[k] = temp_list[i]
i=i+1
else:
alist[k] = temp_list[j]
j=j+1
k=k+1
while i < mid+1:
alist[k] = temp_list[i]
i=i+1
k=k+1
while j < r+1:
alist[k] = temp_list[j]
j=j+1
k=k+1
From what I have been reading online the space complexities of my version and the one you can find at this link https://runestone.academy/runestone/static/pythonds/SortSearch/TheMergeSort.html are O(n). If you do it the way it is done in the link it is easy to make the mistake of assuming space complexity is O(nlogn) but since all the stack frames are not "alive" together it is actually O(n) right ?
My version only creates an additional list of size n every time we are merging so I don't have extra space used on the stack for storing the left and right sublists.
So my questions are:
a) Even though both versions use O(n) space, does mine actually use less space than the one in the book by some constant factor or something ?
b) How about time complexity ? I don't think it has changed... but I am new to this stuff so maybe I screwed it up.
Thanks,
d_darric
python mergesort space-complexity
python mergesort space-complexity
asked Jan 1 at 15:16
d_darricd_darric
388
asked Jan 1 at 15:16
d_darricd_darric
388
edited Jan 1 at 15:22
d_darric
asked Jan 1 at 15:16
d_darricd_darric
388
asked Jan 1 at 15:16
d_darricd_darric
388
asked Jan 1 at 15:16
d_darricd_darric
388
388
Ok but at any point in time I only have one copy of the full list since I only do the merging on the “way up” in the recursion. And as soon as the merge operation is done the stack frame is “killed”. Basically I never have two copies of my list alive at the same time. Which is why I think I am still inO(n)space. Can you tell me where specifically is my reasoning false ?
– d_darric
Jan 1 at 16:03
Please refer to this link <stackoverflow.com/questions/54004903/…> for the answer.
– d_darric
Jan 2 at 19:58
add a comment |
Ok but at any point in time I only have one copy of the full list since I only do the merging on the “way up” in the recursion. And as soon as the merge operation is done the stack frame is “killed”. Basically I never have two copies of my list alive at the same time. Which is why I think I am still inO(n)space. Can you tell me where specifically is my reasoning false ?
– d_darric
Jan 1 at 16:03
Please refer to this link <stackoverflow.com/questions/54004903/…> for the answer.
– d_darric
Jan 2 at 19:58
Ok but at any point in time I only have one copy of the full list since I only do the merging on the “way up” in the recursion. And as soon as the merge operation is done the stack frame is “killed”. Basically I never have two copies of my list alive at the same time. Which is why I think I am still in
O(n) space. Can you tell me where specifically is my reasoning false ?– d_darric
Jan 1 at 16:03
Ok but at any point in time I only have one copy of the full list since I only do the merging on the “way up” in the recursion. And as soon as the merge operation is done the stack frame is “killed”. Basically I never have two copies of my list alive at the same time. Which is why I think I am still in
O(n) space. Can you tell me where specifically is my reasoning false ?– d_darric
Jan 1 at 16:03
Please refer to this link <stackoverflow.com/questions/54004903/…> for the answer.
– d_darric
Jan 2 at 19:58
Please refer to this link <stackoverflow.com/questions/54004903/…> for the answer.
– d_darric
Jan 2 at 19:58
add a comment |
0
active
oldest
votes
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%2f53996585%2fi-have-written-mergesort-2-different-ways-is-the-space-complexity-better-in-one%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f53996585%2fi-have-written-mergesort-2-different-ways-is-the-space-complexity-better-in-one%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
Ok but at any point in time I only have one copy of the full list since I only do the merging on the “way up” in the recursion. And as soon as the merge operation is done the stack frame is “killed”. Basically I never have two copies of my list alive at the same time. Which is why I think I am still in
O(n)space. Can you tell me where specifically is my reasoning false ?– d_darric
Jan 1 at 16:03
Please refer to this link <stackoverflow.com/questions/54004903/…> for the answer.
– d_darric
Jan 2 at 19:58