Let's take integer multiplication and comparison sorting as examples. Despite being roughly comparable in terms of computational complexity, if we look at the set of algorithms which solve each problem, there seem to be stark differences, e.g.,
- Despite there being many different sorting algorithms on paper, there are only a few "ideas." (Recursively sort smaller lists and merge, iteratively build a sorted output, iteratively correct out-of-order pairs.) Other algorithms seem to combine these basic ideas in easily understood ways. (For example, do algorithm $A$ on large inputs and algorithm $B$ on small ones.)
- On the other hand, fast integer multiplication uses heavy machinery not foreshadowed (I think it's fair to say) by the most naive algorithms. By contrast I think we'd be shocked if Fourier transformation turned out to be relevant to the enterprise of comparison sorting.
- Comparison sorting admits elementary algorithms with optimal time complexity, whereas small advances in integer multiplication seem to require new ideas. Why are there no natural comparison sorting algorithms whose complexities lie between $O(n\log n)$ and $O(n^2)$?
So my question is, why is the "algorithmic solution set" of some problems seemingly simple, and other problems complex?
This question is informal, as there is no widely accepted definition of what an algorithm is, let alone when a set of them is "simple" or "complex." However, I find it compelling and I wonder there's been any work in this direction.
(Note that I am not an expert in sorting or multiplication, these are just proxies for the general phenomenon.)
