News for hackers. Stuff that matters.
Re:Lomuto's Comeback by repsilat on Sunday May 17, 2020 @12:27PM (#23213034)
Maybe?

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

So yeah, the author picked the use-cases where this algorithm is going to show in its best light. But that's not bad either, right? Data is often not well-ordered -- if you're counting occurrences of words, and want to get an ordered list (and never mind that you wouldn't use a comparison-based sort for that) you wouldn't expect much order. Likewise sorting any keys/values from a decent hash table.

One worry that I 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.

Re:Lomuto's Comeback by TeMPOraL on Sunday May 17, 2020 @01:43PM (#23213634)
I think one example of extremely unsorted data is random data 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.

Then again, maybe there are algorithms letting you compute percentiles without sorting?

Re:Lomuto's Comeback by leni536 on Sunday May 17, 2020 @02:01PM (#23213802)
If you need k percentile values then I think you could do it in O(n log(k)) with introselect. You most definitely don't need O(n log(n)).
Re:Lomuto's Comeback by loeg on Sunday May 17, 2020 @01:59PM (#23213775)
> Then again, maybe there are algorithms letting you compute percentiles without sorting?

I think you may be able to do so probabilistically, which is often good enough? Additionally, one observation about percentiles is that you don't need to sort all of the data; you can just hold on to the top N results in something like a Heap.

Re:Lomuto's Comeback by kccqzy on Sunday May 17, 2020 @02:19PM (#23213962)
Extracting percentile information doesn't require sorting. Even if you're too lazy to implement anything custom, a few invocations of std::nth_element will likely outperform sorting: https://en.cppreference.com/w/cpp/algorithm/nth_element
Re:Lomuto's Comeback by cozzyd on Sunday May 17, 2020 @02:51PM (#23214273)
Yeah, you can histogram the values if you just need an approximate answer (or if you have few enough discrete values, you can just have a bin per value). Once you have an approximate answer, if you need a more precise answer, you can go through the data again and only consider values within the right bin (which hopefully will be a lot fewer, if you've chosen your bins wisely) and then use something like std::nth_element.