In the 0/1sorting problem, given a sequence S of elements
drawn from a universe E and a characteristic function
f: E → {0,1}, the task is to rearrange
the elements in S so that every element x, for which
f(x) = 0, is placed before any element y, for which
f(y) = 1. Moreover, this reordering should be done
stably without altering the relative order of elements having
the same fvalue, and space efficiently using only
O(1) words of extra space. In this paper we present a generic
algorithm for solving the 0/1sorting problem which works optimally
for many different kinds of sequences and characteristic functions.
The model of computation used is a word RAM with a twolevel memory
hierarchy consisting of an ideal cache and an arbitrarily large main
memory. The performance of our algorithm can be summarized as follows:

Let n denote the length of S. The algorithm performs at most
O(n) element exchanges, invocations of f, and word operations.
 Let w_{ f }(u) denote the amount of work done when applying
f to element u. When the cost of the evaluation of the
characteristic function is not uniform, but depends on the element
f is applied to, the algorithm uses O(∑_{u∈
S} w_{ f }(u)) work under the assumption that element exchanges involve
O(1) work.
 Let B denote the size of cache blocks measured in elements. The
algorithm incurs O(n / B) cache misses in the idealcache model
under the tallcache assumption (excluding the cache misses possibly
generated by the invocations of f).
Interestingly, our algorithm is neither aware of
the characteristics of the cache (hardware obliviousness) nor the
implementation of f (software obliviousness). 