4 ms·

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

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.

TeMPOraL 6y ago
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?
- deleted 6y ago
  [deleted]
- loeg 6y ago
  > 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.
- leni536 6y ago
  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)).
- kccqzy 6y ago
  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 https://en.cppreference.com/w/cpp/algorithm/nth_element
- cozzyd 6y ago
  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.

TeMPOraL 6y ago

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?

deleted 6y ago
[deleted]
loeg 6y ago
> 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.
leni536 6y ago
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)).
kccqzy 6y ago
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 https://en.cppreference.com/w/cpp/algorithm/nth_element
cozzyd 6y ago
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.