The Postman's Sort

Table 1

<B>                    Comparison Sort  Postman's Sort  Speed Factor</B>
<B>-----------------------------------------------------------------</B>
Time fixed key      3<I>N</I>log<SUB>2</SUB><I>N</I>)         4<I>N</I>              .75log<SUB>2</SUB>(<I>N</I>)
Time Variable key   <I>N</I>log<SUB>2</SUB><I>N</I>)log<SUB>26</SUB>(<I>N</I>)  2<I>N</I>log<SUB>703</SUB>(<I>N</I>)     .9log<SUB>2</SUB>(<I>N</I>)
Sort 1KB records    3 sec            3 sec           1.0
Sort 10KB records   27 sec           18 sec          1.5
Sort 100KB records  558 sec          290 sec         1.92