<story><title>Lomuto&apos;s Comeback</title><url>https://dlang.org/blog/2020/05/14/lomutos-comeback/</url></story><parent_chain><item><author>TeMPOraL</author><text>I think one example of extremely unsorted data is &lt;i&gt;random data&lt;/i&gt; in Monte Carlo simulations, in particular if you need to compute statistical summaries that need the data to be sorted - e.g. percentiles. So you may end up repeatedly sorting million-long random arrays many time a second.&lt;p&gt;Then again, maybe there are algorithms letting you compute percentiles without sorting?</text></item><item><author>repsilat</author><text>Maybe?&lt;p&gt;Lots of people replaced their sorting algorithms with Tim-Sort because runs of alrealdy-sorted data are empirically common (at least in some workloads). I&amp;#x27;ve seen it myself, in use-cases where sort keys change slightly from iteration to iteration in some larger algorithm, and sort items need to be dynamically kept in order. It no doubt also happens when grabbing data from multiple places, each of which is theoretically ordered arbitrarily but is in practice ordered predictably.&lt;p&gt;So yeah, the author picked the use-cases where this algorithm is going to show in its best light. But that&amp;#x27;s not bad either, right? Data is often &lt;i&gt;not&lt;/i&gt; well-ordered -- if you&amp;#x27;re counting occurrences of words, and want to get an ordered list (and never mind that you wouldn&amp;#x27;t use a comparison-based sort for that) you wouldn&amp;#x27;t expect much order. Likewise sorting any keys&amp;#x2F;values from a decent hash table.&lt;p&gt;One worry that &lt;i&gt;I&lt;/i&gt; would have applies specifically to C++ and D: sometimes values are big, and copies are expensive. But I guess users can always choose to sort pointers like other languages do, if the standard library uses a copy-heavy, branch-light algorithm.</text></item><item><author>mehrdadn</author><text>Notice that this is on &lt;i&gt;random longs&lt;/i&gt;. Of &lt;i&gt;course&lt;/i&gt; branch misprediction and memory bandwidth is going to crush you for a branchy sort... you&amp;#x27;ll be wrong like half the time, and the comparisons and swapping are trivial! Real world data isn&amp;#x27;t random, so I&amp;#x27;d expect branch predictors to do much better with recognizing patterns. And your sorting isn&amp;#x27;t going to be as simple as sorting integers according to their values all that often. It&amp;#x27;s a neat exercise, but absent more realistic benchmarking to the contrary, I wouldn&amp;#x27;t assume I&amp;#x27;ll get a faster program by just substituting even a typical quicksort with this...</text></item></parent_chain><comment><author>leni536</author><text>If you need k percentile values then I think you could do it in O(n log(k)) with introselect. You most definitely don&amp;#x27;t need O(n log(n)).</text></comment>
<story><title>Lomuto&apos;s Comeback</title><url>https://dlang.org/blog/2020/05/14/lomutos-comeback/</url></story><parent_chain><item><author>TeMPOraL</author><text>I think one example of extremely unsorted data is &lt;i&gt;random data&lt;/i&gt; in Monte Carlo simulations, in particular if you need to compute statistical summaries that need the data to be sorted - e.g. percentiles. So you may end up repeatedly sorting million-long random arrays many time a second.&lt;p&gt;Then again, maybe there are algorithms letting you compute percentiles without sorting?</text></item><item><author>repsilat</author><text>Maybe?&lt;p&gt;Lots of people replaced their sorting algorithms with Tim-Sort because runs of alrealdy-sorted data are empirically common (at least in some workloads). I&amp;#x27;ve seen it myself, in use-cases where sort keys change slightly from iteration to iteration in some larger algorithm, and sort items need to be dynamically kept in order. It no doubt also happens when grabbing data from multiple places, each of which is theoretically ordered arbitrarily but is in practice ordered predictably.&lt;p&gt;So yeah, the author picked the use-cases where this algorithm is going to show in its best light. But that&amp;#x27;s not bad either, right? Data is often &lt;i&gt;not&lt;/i&gt; well-ordered -- if you&amp;#x27;re counting occurrences of words, and want to get an ordered list (and never mind that you wouldn&amp;#x27;t use a comparison-based sort for that) you wouldn&amp;#x27;t expect much order. Likewise sorting any keys&amp;#x2F;values from a decent hash table.&lt;p&gt;One worry that &lt;i&gt;I&lt;/i&gt; would have applies specifically to C++ and D: sometimes values are big, and copies are expensive. But I guess users can always choose to sort pointers like other languages do, if the standard library uses a copy-heavy, branch-light algorithm.</text></item><item><author>mehrdadn</author><text>Notice that this is on &lt;i&gt;random longs&lt;/i&gt;. Of &lt;i&gt;course&lt;/i&gt; branch misprediction and memory bandwidth is going to crush you for a branchy sort... you&amp;#x27;ll be wrong like half the time, and the comparisons and swapping are trivial! Real world data isn&amp;#x27;t random, so I&amp;#x27;d expect branch predictors to do much better with recognizing patterns. And your sorting isn&amp;#x27;t going to be as simple as sorting integers according to their values all that often. It&amp;#x27;s a neat exercise, but absent more realistic benchmarking to the contrary, I wouldn&amp;#x27;t assume I&amp;#x27;ll get a faster program by just substituting even a typical quicksort with this...</text></item></parent_chain><comment><author>loeg</author><text>&amp;gt; Then again, maybe there are algorithms letting you compute percentiles without sorting?&lt;p&gt;I think you may be able to do so probabilistically, which is often good enough?  Additionally, one observation about percentiles is that you don&amp;#x27;t need to sort all of the data; you can just hold on to the top N results in something like a Heap.</text></comment>