К>for(int i=1; i<=N; ++i)
К>{
К> int& here = arr[i-1];
К> while(here != 0 && here != i)
К> swap(here, arr[here-1]);
К>}

Отлично, спасибо! Когда думал о этом варианте решил что скорость будет n!. чета меня зациклило на бинарной арифметике.