Talk:1185: Ineffective Sorts
I loved the "runs in O(n log n)" part. 184.108.40.206 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. 220.127.116.11 00:56, 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.18.104.22.168 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...22.214.171.124 18:00, 14 March 2013 (UTC) 126.96.36.199 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. 188.8.131.52 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 merge (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.184.108.40.206 22:44, 17 March 2013 (
Did nobody notice that the POSIX/UNIX commands are uppercase, when they are supposed to be case-sensitive lowercase? If you actually call system() with those arguments (in Linux), you don't delete anything and just get the "command not found" error. --220.127.116.11 01:41, 21 March 2013 (UTC)
- It's possible they are meant to be lowercase, as parts of this comic appear to be written in Mixed-case Small Caps. Look at the top lines of each program, for example. --Aaron of Mpls (talk) 06:59, 5 April 2013 (UTC)
Did anyone see this hint on the about page (http://xkcd.com/about/):
"Which sorting algorithms should I use? They taught me so many.
This is tricky. Most of what they teach you in school is just as an example of how to think about algorithms; 99% of the time you shouldn't worry about optimizing your sorts. Just learn to implement Quicksort (which is very good) and use that without fretting about it too much. People overfocus on efficiency over clarity and simplicity. And most of the time the environment you're coding in will have an efficient sort function built-in anyway.
Note: If you're interviewing for a company for a position with a focus on algorithms, the above is not an excuse not to know your stuff."