Сортировка подсчетом не теряя данных

[Templar]

Задача такая: Дан массив из структур с ключами нужно выполнить сортировку подсчетом не теряя данных этой структуры.

Пример:

pair<int,mytype> ar[1000000];//тот самый массив int-ключ mytype структура которая должна сохраниться.

Желательно выложить идеи или ссылки.Код с комментариями и пояснениями приветствуется.Заранее спасибо.

[MBo]

что имметс в виду - второй алгоритм отсюда?
http://ru.wikipedia.org/wiki/Сортировка_подсчётом

можете во время подсчета использовать поле .first для организации связного списка элементов с одним и тем же ключем. результат, правда, придется писать в новый массив, не исходный ar, и копировать структуры mytype в него.