Now let's continue with the down-sweep, which will operate on the output of the up-sweep:

input: x0, ..., xn-1
initialize:
    for i = 0 to n - 2:
        yi := xi
    yn-1 := 0
begin:
for k = log2(n) - 1 to 0:
    parfor j = 0 to n - 1: 
        if j is divisible by 2k+1:
            temp := yj+2k-1
            yj+2k-1 := yj+2k+1-1
            yj+2k+1-1 := yj+2k+1-1  temp
        else:
            continue
end
output: y0 , y1 , ..., yn-1