Can a Minimum Possible Efficiency be proven?
There are certainly ways to show that certain algorithms must take a certain amount of time or certain data structures require a certain amount of space. One common way is to use information theory.

An unsorted array is a permutation of the sorted array. There are $n!$ possible permutations. The job of sorting, in an information theoretic sense, is to discover precisely which permutation it is.

To transmit a number between $1$ and $m$ requires transmitting $\log_2 m$ bits of information. To transmit a permutation of $n$ elements, therefore, requires $\log_2 n!$ bits of information. By Stirling's approximation, this turns out to be $n \log_2 n + O(\hbox{low order})$ bits.

A binary comparison operation discovers one bit of information. It follows that any sorting algorithm which only uses a binary comparison operation must perform at least $n \log_2 n + o(n \log n)$ comparisons. If we assume that a comparison takes a constant amount of time, that means that the sort must take at least $\Omega(n \log n)$ time.

A radix sort could beat this by discovering more than one bit of information per query.

A similar argument shows that binary search is optimal. You are trying to find a number between $1$ and $n$, which means discovering $\log_2 n$ bits of information. If your query operation returns one bit of information, you need at least $\log_2 n$ queries to find an element.

It's a similar story with space usage. Suppose that you need to store a permutation in memory. By an identical argument, this requires at least $n \log_2 n + o(n \log n)$ bits of storage. Since you need $\log_2 n$ bits to store an integer between $1$ and $n$, you essentially can't do any better than storing $n$ integers.