<story><title>What’s really so bad about bubble sort?</title><url>http://nicknash.me/2012/10/12/knuths-wisdom/</url></story><parent_chain></parent_chain><comment><author>thaumaturgy</author><text>Since this is the third recent item on HN featuring the impact of branch prediction on code performance, let&apos;s make sure we keep our heads on straight: a good algorithm will outperform a bad algorithm that&apos;s tuned for branch prediction.&lt;p&gt;Quicksort infamously abuses branch prediction, yet is still the standard against which all other sorting algorithms are compared. Some work is being done to improve Quicksort&apos;s branch prediction performance [1], but that&apos;s mostly focusing on choosing better pivots.&lt;p&gt;A &lt;i&gt;perfect&lt;/i&gt; sorting algorithm, something like a very large sorting network, will necessarily make any processor&apos;s branch predictor give up and go home -- and that&apos;ll still be faster to execute than a naive algorithm tuned for branch prediction.&lt;p&gt;[1]: &lt;a href=&quot;http://www.cs.auckland.ac.nz/~mcw/Teaching/refs/sorting/quicksort-branch-prediction.pdf&quot; rel=&quot;nofollow&quot;&gt;http://www.cs.auckland.ac.nz/~mcw/Teaching/refs/sorting/quic...&lt;/a&gt;</text></comment>
<story><title>What’s really so bad about bubble sort?</title><url>http://nicknash.me/2012/10/12/knuths-wisdom/</url></story><parent_chain></parent_chain><comment><author>TheEskimo</author><text>Honestly, bubble sort isn&apos;t &lt;i&gt;that&lt;/i&gt; bad.&lt;p&gt;Couple years ago I had a fairly simple program which collected some data into a linked list and displayed it at the end. It took about 2 seconds to load and process the data from disk. I realized it might be neat to optionally sort the output. Since I didn&apos;t feel like doing serious work, I just added a bubble sort to my linked list which took a comparison function and then bubble-sorted by pointer swapping.&lt;p&gt;Guess what time it added? less than a 10th of a second. Completely negligible. It saved me a few hours (as writing bubble sort for a linked list takes maybe 5 minutes and has no chance of complicated bugs) and I doubt anyone will ever notice any slowdown.&lt;p&gt;So what&apos;s the lesson? Little performance tweaks hardly matter in the average program nowadays because everything&apos;s disk or network bound (IO bound). For the average program it&apos;s not worth writing more complex code that will be quicker (once you fix the hard-to-see bugs) until you actually know the slowness is an issue.</text></comment>