How embarrassing! It looks like I flipped around Fibonacci and factorial in my head when writing my reply. You're completely right that the comparison-based so

How embarrassing! It looks like I flipped around Fibonacci and factorial in my head when writing my reply. You're completely right that the comparison-based sorting bound has nothing to do with Fibonacci numbers. And in fact log_2(n!) is about n*log_2(n), which is where the comparison-based sorting bound comes from. And Fibonacci growth is absolutely exponential, just with an exponent larger than 2.