  In an array of N elements, M positions and M elements are "marked". We show
how to permute the elements in the array so that all marked elements end in
marked positions, in time O(N) (in the standard word-RAM model),
deterministically, and obliviously - i.e. with a sequence of memory accesses
that depends only on N and not on which elements or positions are marked.
  As a corollary, we answer affirmatively to an open question about the
existence of a deterministic oblivious algorithm with O(N) running time for
tight compaction (move the M marked elements to the first M positions of the
array), a building block for several cryptographic constructions. Our O(N)
result improves the running-time upper bounds for deterministic tight
compaction, for randomized tight compaction, and for the simpler problem of
randomized loose compaction (move the M marked elements to the first O(M)
positions) - until now respectively O(N lg N), O(N lg lg N), and O(N lg*N).
