Re: sorting of records with 0 and 1.



From: "c.lang.mys...@xxxxxxxxx" <c.lang.mys...@xxxxxxxxx>
we have an array of n data records to sort and that the key of
each record has the value 0 and 1.

Are the records variable-length, where each record must be
individually parsed from one end to find where the other end is, or
fixed length, with the length also given as a parameter at the very
start? If variable-length, can they also be parsed in the reverse
direction, or only in one direction not the other? If
variable-length, is there a fixed upper-bound on length of records,
or for different sets of records can the largest record be
arbitrarily large and the algorithm must continue to work just the
same as with short records?

The in place sorting algorithm must be stable and run in o(n) time.

By "in place", do you mean o(1) additional storage allowed, such as
for the algorithm/code itself as well as a fixed number of
fixed-size variables such as counters/pointers? No additional
temporary memory may be allocated?

Note: If lengths of records are unbounded, but size of pointer is
fixed, then you have Mission Impossible, because even a single
record can be larger than the entire address range expressible in
that fixed-size pointer. So you need to carefully consider your
answers to get a consistent set of conditions for stating your
question.
.