We design main memory algorithms that sort in worst-case time such that the time varies smoothly from linear to optimal time for files that vary from being nearly sorted and have little disorder to being very unsorted. They are adaptive sorting algorithms. To this end, we:
introduce three basic ways of measuring nearly sortedness or disorder;
give a sorting algorithm, Strip Sort, that is worst-case-optimally adaptive to one of them;
give an axiomatic definition of measures of disorder;
and provide an infinitude of sorting algorithms that can be proved to be adaptive, with respect to many different measures, under some reasonable assumptions.