I've been wondering if research of these algorithms exists. An example, let's say I'm fine with $p$% of possible inputs of size $n$ to be unsorted. Is there an algorithm that would allow me to sort $n$ integers in sublinear time with a guarantee that $(100-p)$% of all possible inputs will be sorted.
Algorithms don't have to be linked the sorting, let's say it's optimization, is there an algorithm that will find the optimal tour for 1% of all TSP inputs of size $n$ really fast and what that algorithm is?
Is there a fundamental reason why these algorithms shouldn't exist or are hard to analyze?