function Y = FFTransform(y)
% usage: Y = FFTransform(y)
% description: This function accepts input vector y of length
% 2^p (NB: assumed and not checked for) to and outputs
% the DFT Y of y using the FFT algorithm.
 
y = y(:); % turn y into a column
N = length(y);
p = log2(N);
omegaN = exp(-pi*i/N).^(0:N-1).'; % all the omegas we need
Y = y(FFTsort(p)); % initial Y at bottom level
stride = 1;
for l=1:p
  omegal = omegaN(1:N/stride:N);
  stride = 2*stride;
  for j=1:stride:N
    evens = Y(j:j+stride/2-1);
    odds = omegal.*Y(j+stride/2:j+stride-1);
    Y(j:j+stride/2-1) = evens + odds;
    Y(j+stride/2:j+stride-1) = evens - odds;
  end
end
Y = Y/N;