Сортировка подсчётом

Название отсылает к алгоритму — если все числа из диапазона от $0$ до $M$, то можно подсчитать количество чисел в исходном массиве, для каждого из чисел от $0$ до $M$. Всего за один цикл! Грубо говоря, сделать второй массив размера $M$, такой массив называют массивом подсчёта, и в $i$-ой ячейки хранить количество $i$ в исходном массиве.

int* cnt = new int[m];
for (int i = 0; i < n; i++) {
  cnt[a[i]]++;
}
int* res = new int[n];
int pos = 0;
for (int i = 0; i < m; i++) {
  for (int j = 0; j < cnt[i]; j++) {
    res[pos++] = i;
  }
}

Стоит использовать, когда диапазон ключей по которому мы хотим сортировать достаточно мал.

На практике, когда вы сортируете массив, то обычного по нему стоит пройти. Не обязательно иметь новый массив, достаточно просто знать количество. Например, если надо лишь вывести отсортированный массив, то сделаем просто cout << i; вместо res[pos++] = i;.

Чтобы отсортировать массив из пар чисел по ключу этих же пар, достаточно сделать подсчёт в двумерном массиве.

¹ : Вместо массива подсчёта, можно сохранять все элементы. В $i$-ой ячейке будем хранить динамический массив. Тем самым можно добиться стабильности. Например, у нас есть массив из классов и надо стабильно отсортировать массив по полю .id.

Не то, чтобы я не знал, как создать динамический массив динамических массивов, но это уже слишком =) Можете прочитать про это тут. Но удобнее использовать std::vector, собственно его всегда удобнее использовать, об этом я писал тут.

Давайте отсортируем массив структур по полю .id выше, как я обещал в самом начале.

struct MyStructure {
  int id;
  string name;
};

// код
vector<vector<MyStructure>> cnt(m);
for (int i = 0; i < n; i++) {
  cnt[a[i].id].push_back(a[i]);
}

Вам может покажется, что сортировка не имеет реального выигрыша даже для $m$ гораздо меньшего $n$, но идея подсчёта является фундаментальной для многих алгоритмов и задач. Самое первое, что мне приходит на ум не самый сложный алгоритм суффиксный массив (сама идея лёгкая, но вот задачи на эту тему достаточно сложные). Кстати, это тоже сортировка!!!