## Ex BibliothecaThe life and times of Zack Weinberg.
## Tuesday, 10 August 2004## # 1:20 PM## another math problemReally an algorithmics problem, I suppose. Some definitions:
for any set - The
*median index**m*is the number ⌊_{s}*n*/2⌋;_{s} - The
*median**M*is the_{s}*m*-th element;_{s} - The
*left half*L(*s*) is the subset consisting of the elements numbered 1 …*m*-1;_{s} - The
*right half*R(*s*) is the subset consisting of the elements numbered*m*+1 …_{s}*n*._{s}
Given a base set *S*- L(
*S*) - R(
*S*) - L(L(
*S*)) - R(L(
*S*)) - L(R(
*S*)) - R(R(
*S*)) - …
and so on until all elements of the original set The preferred solution is a nonrecursive algorithm with O(1) space requirement. |