# Difference between revisions of "Talk:1185: Ineffective Sorts"

(sorts) |
|||

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. |

## Revision as of 22:37, 17 March 2013

I loved the "runs in O(n log n)" part. 76.106.251.87 00:16, 14 March 2013 (UTC)

I lost it on //portability. It's a sad state where I've actually more or less come across 3 of these. 203.126.136.142 00:56, 14 March 2013 (UTC)

Audiovisual aid circa 1981, eh: **http://youtube.com/watch?v=gv0JUEqaAXo#t=236s** 98.111.152.198 01:35, 14 March 2013 (UTC)

One of xkcd's best in a quite a while, imo. Alpha (talk) 03:39, 14 March 2013 (UTC)

Saying "bogosorts actually run in O(n*n!) time and may never finish" is a contradiction. Not the runtime is in O(n*n!), but the *expected* runtime. BKA (talk) 08:19, 14 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.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...193.175.223.10 18:00, 14 March 2013 (UTC) 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. 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.