so what I need is a bit hard to describe for me, so I start with giving a context: I have a list of numbers that is not sorted (yet). One part of a more complex algorithm is that I need a rough approximation of a list of arbitrary numbers so that I can throw a number into that approximation and it returns a likely position in the list (after I sorted the list).
What I am doing right now is to get the smallest and biggest number in the list and just create a straight line through them and use this as my approximation. This way I can "sort in" all the other numbers on the line. As I already mentioned, a rough approximation is sufficient, that is why I need it in linear time (a full sort would require
O(n). My approach with the straight line already delivers acceptable results, but the better my approximation the faster the whole algorithm will run, so my question is: Can I somehow get a more accurate approximation in linear time?