Finding sorted middle 50% of a sequence (in Boost Accumulators or in other data structure) -

for sequence of values, how 1 find sorted middle 50% of sequence in boost accumulators?

for example, let's have following sequence,
25, 21, 9, 13, 17, 19, 12, 29, 50, 97, 10, 11.

the middle 50% data have follows:
13, 17, 19, 21.

of course, 1 can sort sequence, becomes
9, 10, 11, 12, 13, 17, 19, 21, 25, 29, 50, 97.

and 1 can collect middle 50% data.

now, accumulators framework internally store , sort sequence? if yes, possible retrieve value reside in particular index?

reading here, think accumulators framework not store original data , framework not appropriate problem trying solve.

while writing this, find bit foolish try accomplish using accumulators. however, using other purposes , expecting solution in accumulators.

now, possible build data structure efficiently maintain current , sorted middle 50% data in way size of data structure never exceeds half of size of sequence?

thinking while, guess may not possible devise such data structure. @ first thought, thought of values can forgotten/discarded permanently assuming never appear in sorted middle 50%. however, assumption wrong, , values might reappear in sorted middle 50% depending on yet arrive values in sequence.

as @adam rosenfeld pointed out, you're looking hoare's selection algorithm, variant of quick sort.

what didn't point out bit of care, can have put elements care in right place part of selection process.

the selection algorithm partitions data less , greater selected element. example, assume had array of 100 elements, , wanted 25^th. arrange elements first through 24^th elements in array smaller 25^th, 25^th, larger elements. on each side ordered respect 1 element though, not compared each other.

you can still take advantage of middle 50% quickly: first select 25th percentile. specify part above 25^th input, , find element 2/3^rds of way across part. give 25^th, 75^th, , (the important part) of elements values between arranged between elements (though inside of range, order random).