<story><title>Hoare’s Rebuttal and Bubble Sort’s Comeback</title><url>https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubble-sorts-comeback.html</url></story><parent_chain></parent_chain><comment><author>samatman</author><text>&amp;gt; &lt;i&gt;the final surprise is that Bubble Sort takes the crown for small arrays&lt;/i&gt;&lt;p&gt;This didn&amp;#x27;t need to be a surprise! It was a commonplace bit of wisdom in the microcomputer era, when sorting always came with questions about the application.  You can&amp;#x27;t beat it for locality— but you also can&amp;#x27;t beat it for mostly-sorted, small collections.&lt;p&gt;Rather than sorting arrays, the area where bubblesort shines (ok. where bubblesort can still be considered!) is &lt;i&gt;keeping linked lists sorted&lt;/i&gt;, especially where the sort order is important rather than critical. So event queues: you want to float the highest priority to the top, but it&amp;#x27;s ok if occasionally #2 is launched before #1, because events aren&amp;#x27;t guaranteed an execution order.  We&amp;#x27;re using an intrusive linked list because the scheduler has to take what it&amp;#x27;s given, it can&amp;#x27;t lay out memory.&lt;p&gt;Also, any time spent tinkering with an event queue is wasted time. So every round, walk the event queue and perform one (1) bubble sort. This takes the time it takes to traverse the list, effectively. So if you&amp;#x27;ve placed exactly one event at the end of the queue (head of the list), it ends up precisely where it should be. Two? You leave one of them behind for the next pass.&lt;p&gt;It&amp;#x27;s easy to reason out that when the sort starts performing badly, the problem you have is event congestion, not a poor big-O complexity for your queue sort.&lt;p&gt;Bubblesort is sometimes treated as a pessimal joke like bogosort, it isn&amp;#x27;t, it&amp;#x27;s just that the reason it&amp;#x27;s treated as a basic sort pedagogically has been lost, as the profession&amp;#x27;s center of gravity moves away from these kinds of system-level constructs.</text></comment>
<story><title>Hoare’s Rebuttal and Bubble Sort’s Comeback</title><url>https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubble-sorts-comeback.html</url></story><parent_chain></parent_chain><comment><author>FrozenVoid</author><text>Why not use combsort, which is generally
does similar swaps and outperforms bubble sort
 in all cases?
&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Comb_sort&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;en.wikipedia.org&amp;#x2F;wiki&amp;#x2F;Comb_sort&lt;/a&gt;
&lt;a href=&quot;https:&amp;#x2F;&amp;#x2F;www.geeksforgeeks.org&amp;#x2F;comb-sort&amp;#x2F;&quot; rel=&quot;nofollow&quot;&gt;https:&amp;#x2F;&amp;#x2F;www.geeksforgeeks.org&amp;#x2F;comb-sort&amp;#x2F;&lt;/a&gt;</text></comment>