PocketSort

#include <algorithm>
#include <iostream>
#include <vector>
using std::vector;

// Карманная сортировка по последней цифре.
void PocketSort( vector<long long>& arr )
{
    int n = arr.size();
    if( n <= 1 ) {
        return;
    }
    int k = 10;
    // Количества элементов в каждом кармане.
    vector<int> pockets( k, 0 );
    for( int i = 0; i < n; ++i ) {
        ++pockets[arr[i] % 10];
    }
    // Преобразуем в координаты концов карманов + 1.
    // Что то же самое, что начала следующих карманов. pockets[0] не трогаем.
    for( int i = 1; i < k; ++i ) {
        pockets[i] += pockets[i - 1];
    }

    // Перемещаем элементы в результирующий массив с карманами.
    vector<long long> result( n );
    for( int i = n - 1; i >= 0; --i ) {
        int targetIndex = --pockets[arr[i] % 10];
        result[targetIndex] = arr[i];
    }

    // Меняем местами. Старый удалится в деструкторе result.
    std::swap( arr, result );
}

int main()
{
    int n = 0;
    std::cin >> n;
    vector<long long> arr( n, 0 );
    for( int i = 0; i < n; ++i ) {
        std::cin >> arr[i];
    }

    PocketSort( arr );

    for( int i = 0; i < n; ++i ) {
        std::cout << arr[i] << " ";
    }
    return 0;
}