Suggestion for speeding up Sort (GNU CoreUtils 7.4)

[N . Shamsundar]

This is a suggestion to speed up Sort, rather than a bug report.

The addition of the code given below at the entry to function mergelines() of 
GNU Sort will exploit of the special relation between the arguments (HI - NHI = 
T - (NLO + NHI)) to replace the merge operation with a less expensive copy 
operation if it so happens that the last element of LO and the first element of 
HI are in order with respect to each other. Since the two subarrays are already 
sorted, the merging can be accomplished with a simple memory copy.

    if(compare (lo - nlo, hi - 1) <= 0){
                     /* Skip merge */
        if (t - lo) do *--t = *--lo; while  (--nlo);
        return;
        }

Sincerely,

N. Shamsundar
Assoc. Professor (Retd.)
University of Houston