It is necessary to implement the fastest possible sorting algorithm for a bit array (0 and 1) with the ability for 100% reverse recovery.
Task essence:
We have an array of 0s and 1s (up to 8 MB)
It needs to be sorted: all 1s on the left, all 0s on the right → "111...000"
But without losing the original order:
that is, it is necessary to preserve only the rank of the permutation, not the full list of positions
Key requirements:
Without saving the list of positions of 1s
Only rank (unique permutation number)
Rank must be converted into a short seed (for example, 60 characters)
It must be possible to restore the full original order from seed + N + K
If you can implement the reverse function unrank() — that’s a plus
GMP, OpenMP, SIMD, etc. can be used
Required skills:
Excellent knowledge of C or C++
Experience with ranking algorithms, combinations, permutations
Knowledge of combinatorics (C(n, k)) in practice
Experience working with large numbers (__int128, GMP or Boost)
Performance optimization (multithreading, SIMD, caching)