Each division will take O(1) time. In first stage there is only 1 division, next stage there are 2 divisions, then 4 then 8 and so on. In last stage we need loglogN divisions.
We can write each division size of last stage N/logN = N/(2loglogN).
So we get series like 1+21+22+23+24+....+loglogN ( loglogN = 2logloglogN ) . Now by solving the G.P series we get O(loglogN).