An almost sorted sequence could be one with at most a linear number of inversions.