Hacker News new | past | comments | ask | show | jobs | submit login

Only in the random case. Already sorted in either direction and it's ~10x slower.

Who wants to sort sorted data. If the input data is more often sorted, you can test this before sorting.

Data can be partially sorted and it happens quite often. As I understood, it's exactly the purpose of quadsort - to leverage locally ordered sequences.

Sort your data. Store it somewhere and then later add more unsorted data.

Sorting sorted or mostly-sorted arrays is not uncommon in many use cases.

"Mostly-sorted" is a very vague definition.

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

According to this definition, the "random tail" test data is not "mostly sorted".

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

Applications are open for YC Summer 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact