1 067 KB
used 30 bit structure with queue
struct cell {
   unsigned value : 30;
   cell (unsigned in) : value (in) {};
};
std::queue <cell> major;
ok, queue build with pointers, so lets soluted witout it

971 KB
used 30 bit structure with vector
std::vector <cell> major;
hm...
ok let's try other way


used indexing of values - there are 100'000 posible values, so let's indexing every value and storage indexes
std::map <int, int> i2v, v2i;
1 223 KB

bad way, well let's make crazy thing - build bit storage with next structure - for every value calculate number of max bit with help of next function
int length (unsigned in) {
   int result (0);
   while (in) {
      ++result;
      in >>= 1;
   };
   return result;
};
than push into storage last {length (value)} bits of value and than 5 bits, which content number of bits of this value (maximum value is 1'000'000 so maximum count of bits is 30, thats why counter of bits count must have 5 bits)
ok for example if PUSH value 5 [101]
length (5) return 3, we push into storage bits [101] and than five bits with length of value bits - 3 [00011]
std::list <unsigned char> major;
783 KB

...
yeah, last idea - use bit storage and indexing values
803 KB

guys, who solved this problem with C++ - you are genius, I am out of ideas, have smb other one ?

I solved it on 400KB but not very fast
I added data by 1000 size portions and was making
stable sort