Newsgroups: sci.math
From: hoey@aic.nrl.navy.mil (Dan Hoey)
Date: 1995/05/24
Subject: Re: pleas ehelp with this "simple" puzzle

u9014...@muss.cis.McMaster.CA (M.S. Chan) writes:

> If you are using sort by comparsion, then the minimum number of
> comparsion required - no matter how smart the algorithm is - is O(n log
> n), where log is log to the base 2.

He wasn't counting comparisons.  He was counting "moves", in which a
move is the reversal of some initial segment of the sequence.  Your
upper bound is not accurate for this measure.

Dan Hoey
Hoey@AIC.NRL.Navy.Mil