TheUNIXSystem: Theory and Practice in the Construction of a Working Sort Routine

Abstract

Because comparison in the standard UNIX™ operating system sort routine, /bin/sort, is interpretive, it is generally more time-consuming than the standard paradigm of comparing two integers. When a colleague and I modified sort to improve reliability and efficiency, we found that techniques that improved performance for other sorting applications sometimes degraded the performance of sort. Input and output are important when comparisons are simple, but as comparisons become more complex, the number of comparisons quickly dominates the performance of sort.