Editing Talk:1185: Ineffective Sorts
Please sign your posts with ~~~~ |
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 10: | Line 10: | ||
:Not necessarily. O(n*n!) is the expected runtime, but unlike other sorts, there is no max runtime which is what it is trying to say.[[Special:Contributions/206.181.86.98|206.181.86.98]] 03:09, 15 March 2013 (UTC) | :Not necessarily. O(n*n!) is the expected runtime, but unlike other sorts, there is no max runtime which is what it is trying to say.[[Special:Contributions/206.181.86.98|206.181.86.98]] 03:09, 15 March 2013 (UTC) | ||
Didn't the author of the halfhearted merge sort give up on the sort part of the merge sort? 'cause merging is done in the return[a,b] part as far is see it...[[Special:Contributions/193.175.223.10|193.175.223.10]] 18:00, 14 March 2013 (UTC) | Didn't the author of the halfhearted merge sort give up on the sort part of the merge sort? 'cause merging is done in the return[a,b] part as far is see it...[[Special:Contributions/193.175.223.10|193.175.223.10]] 18:00, 14 March 2013 (UTC) | ||
− | [[Special:Contributions/206.181.86.98|206.181.86.98]] 03:09, 15 March 2013 (UTC)Well return[a,b] merges them in exactly the original order. So I think you are right. It recursively cuts the list into tiny bits and returns the uncut back to the previous call. [[Special:Contributions/206.181.86.98|206.181.86.98]] 03:09, 15 March 2013 (UTC) | + | [[Special:Contributions/206.181.86.98|206.181.86.98]] 03:09, 15 March 2013 (UTC)Well return[a,b] merges them in exactly the original order. So I think you are right. It recursively cuts the list into tiny bits and returns the uncut back to the previous call. [[Special:Contributions/206.181.86.98|206.181.86.98]] 03:09, 15 March 2013 (UTC) The list is sorted when the already sorted sublists are merged. This is an efficient way to sort because only the lowest values in each sublist need to be compared so fewer comparisons are required. The author of the halfhearted merge sort did not write a proper mege (or any merge) and instead returns the sublists in the original order. Sublists of length one are known to be in the correct order which is why the list is recursively cut into units of length one. |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |