> Of course this is a n^2 sort. Isn't it exponential? An n element sort calls two n-1 element sorts. Each of those calls two n-2 element sorts, and so on. So y

> Of course this is a n^2 sort. Isn't it exponential? An n element sort calls two n-1 element sorts. Each of those calls two n-2 element sorts, and so on. So you get 2^n total calls, if I'm not mistaken. That is also why the page asks if you can beat it with a function of equal length but subexponential runtime.