На самом деле я считаю, что сортировка подсчетом самая простая и самая нужная сортировка, которую нужно знать, например я находил решения довольно сложных для меня задач именно при помощи сортировки подсчетом, могу привести пример:

Задачу 1546C - AquaMoon and Strange Sort я например решил при помощи сортировки подсчетом, так как у неё были маленькие ограничения по числам на футболках (всего до 1e5), я решил создать два массива, где учитывал четные и нечетные индексы массива, а потом пробегался уже по отсортированному масиву и вычитал 1, если индекс стоит на четной позиции из массива с четными номерами (то есть even[a[i]] -= 1) и то же самое делала с нечетными индексами.

Итог:

#include <bits/stdc++.h>

#define ll long long
using namespace std;
inline string solve(vector<int> &odd, vector<int> &even, vector<int> a, int n){
    for (int i = 0; i < n; ++i) {
        if (even[a[i]] != 0){
            if (i % 2 == 0){
                even[a[i]]--;
            }
        }
        if (odd[a[i]] != 0){
            if (i % 2 != 0){
                odd[a[i]]--;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (even[a[i]] != 0 || odd[a[i]] != 0){
            return "NO";
        }
    }
    return "YES";
}
signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for(int i = 0; i < n; i++) cin >> a[i];
        vector<int> odd(1e5 + 1, 0), even(1e5 + 1, 0);
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0){
                even[a[i]] += 1;
            }else{
                odd[a[i]] += 1;
            }
        }
        sort(a.begin(), a.end());
        cout << solve(odd, even, a, n) << "\n";
    }
    return 0;
}

Мне бы очень хотелось узнать какие алгоритмы вы считаете незаменимыми и чаще всего используете ;)