One simple algorithm: the *bubble-sort*. Given a sequence of
numbers, scan along it until you find a pair that's out of order.
Interchange them. Go back to the start, and scan again. Repeat until all
numbers are sorted. The time this takes increases (on average) with the
square of the number of numbers.

Can we do better? Yes. I think the best possible algorithm that works by comparing pairs of numbers has a time which increases as , where is the number of numbers input.

Wed Feb 14 23:47:23 GMT 1996