Int i,j;

int *c=new int[n]; // массив счетчиков

// обнулим счетчики

for(i=0; i<n; i++) c[i]=0;

// фаза подсчета

for(i=0; i<n; i+){

for(j=0; j<i; j++){

if(t[i]>t[j]){

c[i]++;

} else {

c[j]++;

}

}

}

// фаза расстановки

for(i=0; i<n; i++){

while(i!=c[i]){ // до тех пор, пока t[i] не займет

// окончательного положения

swap(t[i],t[c[i]]); // обмен местами эл-тов таблицы

swap(c[i],c[c[i]]); // обмен местами счетчиков

}

}

}

Ключ t_i в исходной последовательности сравнивается с iпредшест­вующими ключами и, следовательно, общее число сравнений равно

то есть пропорционально N².