comparison sorts may run faster on some lists; many adaptive sorts such as insertion sort run in o("n") time on an already-sorted or nearly-sorted list. the ω("n" log "n") lower bound applies only to the case in which the input list can be in any possible order.