FFT returning values in wrong order

Well, you could count this as a continuation of my thread on the GD board, but now my question is MUCH more C# specific, and therefore I decided to go ahead and post it here.

I am nearly done with the program now...I only have one bug remaining.

When I do the FFT of an array of values, I get all the correct values returned to me, but in the wrong order.

They should be returned in the order:

1 2 3 4

I get them back in the order:

1 4 3 2

Here is my FFT code:

Code:

`static ArrayList FFT(ArrayList a)`

{

//Check the length of the list that has been passed to us

int n = a.Count;

if (n == 1)

return a;

//Create omega

Complex myE = new Complex ( Math.E, 0 );

Complex exponent = new Complex ( 2.0 * Math.PI / (double)n );

Complex omega_n = Complex.Pow(myE, exponent * Complex.I);

Complex omega = new Complex(1, 0);

//Create even/odd lists

ArrayList even = new ArrayList(0);

ArrayList odd = new ArrayList(0);

for (int i = 0; i < a.Count; i++)

{

if (i % 2 == 0)

even.Add(a[i]);

else odd.Add(a[i]);

}

//Recurse

ArrayList Aeven = FFT(even);

ArrayList Aodd = FFT(odd);

//Combine lists

ArrayList Areturn = new ArrayList(n);

for (int k = 0; k < n; k++)

Areturn.Insert(k, Complex.Zero);

for ( int k = 0; k <= ((n / 2) - 1); k++ )

{

Areturn[k] = (Complex)Aeven[k] + omega * (Complex)Aodd[k];

Areturn[k + (n / 2)] = (Complex)Aeven[k] - omega * (Complex)Aodd[k];

omega = omega * omega_n;

}

//Return

return Areturn;

}

How can I change the code to get the result in the right order??