I've seen all the O(n^2) worst case algorithms that reduce to O(n) on nearly sorted lists used, for example, in sweep and prune algorithms in computational geometry.