4 ms·
Who wants to sort sorted data. If the input data is more often sorted, you can test this before sorting.
by chkas 7y ago
Who wants to sort sorted data. If the input data is more often sorted, you can test this before sorting.
- simias 7y agoSorting sorted or mostly-sorted arrays is not uncommon in many use cases.
- chkas 7y ago"Mostly-sorted" is a very vague definition.
- seanhunter 7y agoUsually what people mean by mostly sorted in CS is that there is some small K such that each element in the input is no more than K places from the position it would be in if the input was sorted.
- chkas 7y agoAccording to this definition, the "random tail" test data is not "mostly sorted".
- seanhunter 7y agoWell you could extend the definition to allow a small number of items which are entirely out of place. The point is that the right sort algorithm depends a lot on tthe distribution of input data and how much you care about worst-case vs average case trade offs.
- dgudkov 7y agoData can be partially sorted and it happens quite often. As I understood, it's exactly the purpose of quadsort - to leverage locally ordered sequences.
- imtringued 7y agoSort your data. Store it somewhere and then later add more unsorted data.