Re: [Metakit] multi-column sorting a real answer

[Brian Kelley]

How about another stupid answer.   Suppose you have N perumation columns 
with M entries.  Each permutation column contains the row's order if 
that column was the sort column.  One caveat, you will need to have 
identical values have the same perumation order.  In either case

Form an integer for each of size N*int(log2(M)+1) bits in order of the 
ordered primary keys.  Sort these using a radix-log2(M) sort or 
big-integer sort. 

Example:

N1 N2 N3 => integer value
0    3     0         001100
0    1     1         000101
1    2     2         001010
2    2     3         101011
3    2     3         110101
and use a radix-2 sort on the integer values.

This preperation step is O(N) but potentially memory intensive.  Four 
keys on a million records using five keys would be 5 * 
int(log(1000000)+1) * 1000000 = 70,000,000 or ~70MB.  Actually, that's 
not too bad.

The problem comes when the number of bits to represent M gets larger and 
larger, but this grows logarithmically.

Brian

_____________________________________________
Metakit mailing list  -  [EMAIL PROTECTED]
http://www.equi4.com/mailman/listinfo/metakit