The Quantum Fourier Transform consists of 2 gates. Controlled Phase Gates, and Hadamard gates. I'm assuming the Controlled Phase Gate is a combination of a Control Gate, and a Phase Gate.
But what is the order of operations on the Controlled Phase Gate? CNOT then Phase Change? Or Phase Change then CNOT?
You seem to have confused the CNOT gate with the controlled phase gate. There's no CNOT gate involved in the implementation of a C-phase-gate (let's denote it CPG for short), as all we do with it, is multiplying by a phase factor. For example on two qubits it is defined as:
$$ U_{CPG}(\phi) |xy\rangle = \exp(i(x\land y)\phi)|xy\rangle $$ Where $\land$ is the logical AND operation. Thus the multiplication by the phase factor $e^{i\phi}$ is only applied if the 2 input qubits are $|xy\rangle = |11\rangle.$ All 3 other possible inputs ($00$, $01$, $10$) remain unaffected. Its matrix form using $|00\rangle,$ $|01\rangle,$ $|10\rangle$ and $|11\rangle$ vectors as an orthonormal basis in $\mathbb{C}^4$ would be: \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^{i\phi} \end{pmatrix}
Now in the Quantum Fourier Transform (QFT) setup, single qubit controlled phase gates are used. For example for the first qubit, after the Hadamard, we start by applying the first CPG gate, usually named $R_2=U_{CPG}(2\pi/2^2)$: \begin{pmatrix} 1 & 0 \\ 0 & e^{i2\pi/2^2} \end{pmatrix} Then we continue applying the remaining CPG's, i.e. $R_3,...$ all the way up to $R_k$ (for $k$ qubit quantum computer). Note $R_k$ is given by: \begin{pmatrix} 1 & 0 \\ 0 & e^{i2\pi/2^k} \end{pmatrix} You proceed similarly for the remaining input qubits, until the last qubit for which there's only a Hadamard to apply.
