# Why does merge sort work for any $n$, but the basic FFT algorithm only for powers of $2$?

Merge sort and FFT are both divide and conquer algorithms that split the input in two repeatedly. While merge sort can be applied to any $$n$$, the FFT algorithm given in CLRS (section 30.2, third edition) only applies when $$n$$ is a power of $$2$$. How come we can forge ahead with any $$n$$ for merge sort, but not quite for FFT?

• I think the recursive step works fine, but the problem is the halving lemma (lemma 30.5) Nov 25 at 1:07
• Hi @Rohit, I think you're right, at least for $n$ odd. The first edition even says about the Halving lemma, "if $n>0$ is even,...". Again, for $n$ odd, when you take powers greater than $n/2$, you run into problems, since $\left( \omega_{n/2} \right)^{n/2 +1}$ presents problems if you consider the Cancellation lemma. You would be essentially trying to get an odd power from an even power, or vice versa. Nov 25 at 4:14

The FFT works on pairs of elements, with no leftovers. So there must be an even number of them, and by recurrence, a power of $$2$$.
Variants of the FFT can be based on other primes, and can be combined to work for composite $$n$$, but they don't reach the efficiency of binary FFT.