On Tue, 13 Dec 2005, Dann Corbit wrote:
> The test is designed especially for database systems, which are likely
> to be clustered on data or index (and in the general case are sometimes
> loaded in physically sorted order). In the clustered case, the only
> time the data will not be ordered is when there has been a page split
> and the statistics have not been updated.
>
> The in-order check happens only once and there will not be a significant
> performance hit for removal (except that it will be absurdly fast when
> the data is already ordered or in reverse order if left as-is.)
>
> Ordered and reverse-ordered are two cases where qsort goes quadratic
> (without a test). Of course, introspective sort does not suffer from
> this defect, even with the test removed.
>
Yeah, I would think O(n) in-order check doesn't matter for random data
set. For nearly-ordered set, may be not true. I am not good at C++, so can
you patch the test program with your sort method and the page-split-data
generator? I would be happy to give it a test.
Regards,
Qingqing