7.2.1 Regular and Irregular

		static int  intervalsearch(const void *key, const void *fenceposts, size_t nfence,                sizet elem_size, int (*compar)(const void *, const void *)){    int l, h;        1  =  0;    h  =  nfence;    while( l<h ){      const void *post;      int i;      i = (l+h)/2;      post = (const char *)fenceposts + i*elem_size;      if( (*compar)(key, post) < 0 )        h   i;      else        1 = i+1;    }    return 1;  }

		Program  9.6:

		A function to perform a binary search for an interval. The binary search converges by iteratively testing the midpoint between a lower bound 1 and an upper bound h, and updating one o f the bounds accordingly. The value returned is zero if key<fenceposts [0], or it is nfence if key>=fenceposts nfence-1], or it has the property that key>=fenceposts answer-1] and  key<fenceposts[answer].

		bled by first calling MPI_Alltoall, and looping over the processes one more time. After that, all that remains is to reset the fields in the parray structure and to call the C-library qsort to complete the local sort within each process' local memory.

		9.5 Analysis of a More General Sort

		The program described in the previous section is considerably more complicated than that of Section 9.1. It invokes more MPI collective communication routines, and is subject to statistical fluctuations in the resulting load balance based on the details of the randomly chosen fenceposts. In fact, there is a complex tradeoff between the cost of selecting more fenceposts and the benefit of improving the load balance by using more samples.

		Nevertheless, the times and overheads shown in Figure 9.6 are still very encouraging. The problem scales well up to twelve processors for N=3M and above. It may well be sufficient to stop here and live with overheads of 30% or less. It is unlikely that overall performance can ever be improved (for these problem sizes and machine parameters) by more than 30%, which may not justify additional