Why is finding minimum number of comparisons to sort $n$ elements so difficult?
Let's say the size of the array is such that there are $2^{k-1} &lt; x ≤ 2^k$ possible permutations, so the theoretical lower bound to sort this array is k comparisons. 

Any comparison divides the set of possible permutations in two subsets, consistent with each outcome of the comparison. You'd first need a comparison that splits the set of all possible permutations into two subsets, each of size at most $2^{k-1}$. And each subset you need to split into two subsets of size at most $2^{k-2}$ etc. If these subsets don't have the same size, then after j comparisons the size of the largest subset could exceed $2^{k-j}$, and you lost.