Python merge sort for a list containing distinct valuesMerge sort in PythonMerge sort Python...
If the Captain's screens are out, does he switch seats with the co-pilot?
Why is this plane circling around the Lucknow airport every day?
What Happens when Passenger Refuses to Fly Boeing 737 Max?
How do I express some one as a black person?
Are babies of evil humanoid species inherently evil?
What to do when during a meeting client people start to fight (even physically) with each others?
How to pass a string to a command that expects a file?
Why does Captain Marvel assume the people on this planet know this?
Why do different render engines generate different z pass?
Is having access to past exams cheating and, if yes, could it be proven just by a good grade?
Virginia employer terminated employee and wants signing bonus returned
Grey hair or white hair
What is the likely impact of grounding an entire aircraft series?
Exporting list of URLs
What wound would be of little consequence to a biped but terrible for a quadruped?
Placing subfig vertically
PTIJ: Why can't I eat anything?
Rejected in 4th interview round citing insufficient years of experience
Word for a person who has no opinion about whether god exists
infinitive telling the purpose
How did Alan Turing break the enigma code using the hint given by the lady in the bar?
Do f-stop and exposure time perfectly cancel?
Good allowance savings plan?
How to clip a background including nodes according to an arbitrary shape?
Python merge sort for a list containing distinct values
Merge sort in PythonMerge sort Python implementationMerge sort implementation in PythonMerge Sort Algorithm PythonRecursive merge sort in pythonPython Merge Sort ImplementationMerge sort a given list in PythonMerge sort approach in PythonPython merge sortLinked-list natural merge sort in Python
$begingroup$
This code below is what I think should be the implementation of merge sort in Python and it works as expected. It sorts the given list, where we can safely assume that all values are distinct. But after considering some online implementations I am doubtful about mine. So the base question is "Is this even Merge sort?".
def merge(arr):
# base case
length = len(arr)
half = length//2
if length == 1 or length == 0:
return arr
# recursive case
firstHalf = merge(arr[:half]) # sort first half
secondHalf = merge(arr[half:]) # sort second half
length_firstHalf = len(firstHalf)
length_secondHalf = len(secondHalf)
sortedList = []
i, j = 0, 0 # variables for iteration
while i != length_firstHalf and j != length_secondHalf: # add elements into the new array until either of then two sub arrays is completely traversed
if firstHalf[i] > secondHalf[j]:
sortedList.append(secondHalf[j])
j += 1
continue
if firstHalf[i] < secondHalf[j]:
sortedList.append(firstHalf[i])
i += 1
return(sortedList + firstHalf[i:] + secondHalf[j:]) # return the array after adding whats left of sub array which wasnt completely traversed
python mergesort
edited 10 mins ago
200_success
130k17153419
asked 25 mins ago
billi_meowbilli_meow
112
New contributor
billi_meow is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
This code below is what I think should be the implementation of merge sort in Python and it works as expected. It sorts the given list, where we can safely assume that all values are distinct. But after considering some online implementations I am doubtful about mine. So the base question is "Is this even Merge sort?".
def merge(arr):
# base case
length = len(arr)
half = length//2
if length == 1 or length == 0:
return arr
# recursive case
firstHalf = merge(arr[:half]) # sort first half
secondHalf = merge(arr[half:]) # sort second half
length_firstHalf = len(firstHalf)
length_secondHalf = len(secondHalf)
sortedList = []
i, j = 0, 0 # variables for iteration
while i != length_firstHalf and j != length_secondHalf: # add elements into the new array until either of then two sub arrays is completely traversed
if firstHalf[i] > secondHalf[j]:
sortedList.append(secondHalf[j])
j += 1
continue
if firstHalf[i] < secondHalf[j]:
sortedList.append(firstHalf[i])
i += 1
return(sortedList + firstHalf[i:] + secondHalf[j:]) # return the array after adding whats left of sub array which wasnt completely traversed
python mergesort
edited 10 mins ago
200_success
130k17153419
asked 25 mins ago
billi_meowbilli_meow
112
New contributor
billi_meow is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
$begingroup$
@200_success thank you for the advice, the code is edited now
$endgroup$
– billi_meow
16 mins ago
$begingroup$
@200_success now its okay i believe
$endgroup$
– billi_meow
13 mins ago
$begingroup$
@200_success thank you for editing. much better now
$endgroup$
– billi_meow
6 mins ago
add a comment |
$begingroup$
This code below is what I think should be the implementation of merge sort in Python and it works as expected. It sorts the given list, where we can safely assume that all values are distinct. But after considering some online implementations I am doubtful about mine. So the base question is "Is this even Merge sort?".
def merge(arr):
# base case
length = len(arr)
half = length//2
if length == 1 or length == 0:
return arr
# recursive case
firstHalf = merge(arr[:half]) # sort first half
secondHalf = merge(arr[half:]) # sort second half
length_firstHalf = len(firstHalf)
length_secondHalf = len(secondHalf)
sortedList = []
i, j = 0, 0 # variables for iteration
while i != length_firstHalf and j != length_secondHalf: # add elements into the new array until either of then two sub arrays is completely traversed
if firstHalf[i] > secondHalf[j]:
sortedList.append(secondHalf[j])
j += 1
continue
if firstHalf[i] < secondHalf[j]:
sortedList.append(firstHalf[i])
i += 1
return(sortedList + firstHalf[i:] + secondHalf[j:]) # return the array after adding whats left of sub array which wasnt completely traversed
python mergesort
edited 10 mins ago
200_success
130k17153419
asked 25 mins ago
billi_meowbilli_meow
112
New contributor
billi_meow is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
This code below is what I think should be the implementation of merge sort in Python and it works as expected. It sorts the given list, where we can safely assume that all values are distinct. But after considering some online implementations I am doubtful about mine. So the base question is "Is this even Merge sort?".
def merge(arr):
# base case
length = len(arr)
half = length//2
if length == 1 or length == 0:
return arr
# recursive case
firstHalf = merge(arr[:half]) # sort first half
secondHalf = merge(arr[half:]) # sort second half
length_firstHalf = len(firstHalf)
length_secondHalf = len(secondHalf)
sortedList = []
i, j = 0, 0 # variables for iteration
while i != length_firstHalf and j != length_secondHalf: # add elements into the new array until either of then two sub arrays is completely traversed
if firstHalf[i] > secondHalf[j]:
sortedList.append(secondHalf[j])
j += 1
continue
if firstHalf[i] < secondHalf[j]:
sortedList.append(firstHalf[i])
i += 1
return(sortedList + firstHalf[i:] + secondHalf[j:]) # return the array after adding whats left of sub array which wasnt completely traversed
python mergesort
python mergesort
edited 10 mins ago
200_success
130k17153419
asked 25 mins ago
billi_meowbilli_meow
112
New contributor
billi_meow is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 10 mins ago
200_success
130k17153419
asked 25 mins ago
billi_meowbilli_meow
112
New contributor
billi_meow is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 10 mins ago
200_success
130k17153419
edited 10 mins ago
200_success
130k17153419
edited 10 mins ago
200_success
130k17153419
130k17153419
asked 25 mins ago
billi_meowbilli_meow
112
New contributor
billi_meow is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 25 mins ago
billi_meowbilli_meow
112
asked 25 mins ago
billi_meowbilli_meow
112
112
New contributor
billi_meow is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
billi_meow is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
billi_meow is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$begingroup$
@200_success thank you for the advice, the code is edited now
$endgroup$
– billi_meow
16 mins ago
$begingroup$
@200_success now its okay i believe
$endgroup$
– billi_meow
13 mins ago
$begingroup$
@200_success thank you for editing. much better now
$endgroup$
– billi_meow
6 mins ago
add a comment |
$begingroup$
@200_success thank you for the advice, the code is edited now
$endgroup$
– billi_meow
16 mins ago
$begingroup$
@200_success now its okay i believe
$endgroup$
– billi_meow
13 mins ago
$begingroup$
@200_success thank you for editing. much better now
$endgroup$
– billi_meow
6 mins ago
$begingroup$
@200_success thank you for the advice, the code is edited now
$endgroup$
– billi_meow
16 mins ago
$begingroup$
@200_success thank you for the advice, the code is edited now
$endgroup$
– billi_meow
16 mins ago
$begingroup$
@200_success now its okay i believe
$endgroup$
– billi_meow
13 mins ago
$begingroup$
@200_success now its okay i believe
$endgroup$
– billi_meow
13 mins ago
$begingroup$
@200_success thank you for editing. much better now
$endgroup$
– billi_meow
6 mins ago
$begingroup$
@200_success thank you for editing. much better now
$endgroup$
– billi_meow
6 mins ago
add a comment |
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
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: "196"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
});
}
});
billi_meow is a new contributor. Be nice, and check out our Code of Conduct.
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%2fcodereview.stackexchange.com%2fquestions%2f215298%2fpython-merge-sort-for-a-list-containing-distinct-values%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
billi_meow is a new contributor. Be nice, and check out our Code of Conduct.
billi_meow is a new contributor. Be nice, and check out our Code of Conduct.
billi_meow is a new contributor. Be nice, and check out our Code of Conduct.
billi_meow is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Code Review Stack Exchange!
- 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.
Use MathJax to format equations. MathJax reference.
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%2fcodereview.stackexchange.com%2fquestions%2f215298%2fpython-merge-sort-for-a-list-containing-distinct-values%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
$begingroup$
@200_success thank you for the advice, the code is edited now
$endgroup$
– billi_meow
16 mins ago
$begingroup$
@200_success now its okay i believe
$endgroup$
– billi_meow
13 mins ago
$begingroup$
@200_success thank you for editing. much better now
$endgroup$
– billi_meow
6 mins ago