5 ms·
Only in the random case. Already sorted in either direction and it's ~10x slower.
by pvidler 7y ago
Only in the random case. Already sorted in either direction and it's ~10x slower.
- chkas 7y agoWho 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.