[BusyBox] Re: [PATCH] Re: Sigh... this time i attached the file (bunzip-4.c)

[Manuel Novoa III]

Rob,

On Fri, Oct 24, 2003 at 08:09:00AM -0500, Rob Landley wrote:
> 
> Actually, the n*log(n) shell sort you suggested earlier works well enough for 
> my purposes.  Sorting one 900k block of data (which will be after run length 
> compression, so it's usually rather a lot more data than that) takes a little 
> over 13 seconds of user time (worst case, all zeroes) and 8.15 seconds tested 
> with random data.  (This is on a 900 mhz celeron laptop; not unreasonably far 
> off from the times bzip itself is getting, although I haven't torn apart and 
> instrmented bzip's block sorting stuff yet...)
> 
> The shell sort uses no more data than the 900k of charcters and the index 
> array.  I also whipped up a couple of GET_IDX and SET_IDX functions that only 
> use 20 bits for each index array entry instead of 32 (bringing the total 
> block sorting memory usage down to 3125000 bytes), but all the extra anding, 
> oring, and bit-shifting bloated the worst-case sort time to 22 seconds for a 
> 900k block of zeroes...

Am I missing something here?  You want to (stably) sort a 900k block of
bytes.  Why would you use an O(n*log(n)) general purpose sort when you
can do that in O(n)?

Manuel