Sorting routines

[Bill Baxter]

BCS wrote:
> Reply to Bill,
> 
>> Anyone have a sort routine that can operate simultaneously on multiple
>> arrays of data?
>>
>> It's basically a lexical sort kind of thing, but all the keys and
>> values
>> are in different arrays:
>> int[] key1;
>> int[] key2;
>> ValueT1[] values;
>> ValueT2[] other_values;
>> Datum i is made up of (key1[i],key2[i],values[i],other_values[i]).
>>
>> But they're all stored in separate arrays rather than interleaved in a
>> struct.
>>
>> The goal is to avoid copying the whole mess to an interleaved array in
>> order to sort it, and then copying it back to separate arrays.
>>
>> --bb
>>
> 
> I don't known of one but... This is ugly... make struct that has just a 
> pointer to the key and an int. set the opCmp to chain to the key and 
> then fill an array with them referencing the keys. Then fill the ints 
> with 0 to whatever. When the thing is sorted you have the index map. 
> from there you can get fancy and do an in place reorder (double yuck) or 
> copy each array and move the items back into the correct cells (or if 
> you don't care, do the reorder on the way out and swap in the new array 
> for the old).
> 
> How this will compare to a real multi-array sort will depend on a lot of 
> things.

Hmm.  Oh well.  I don't really want to have to allocate a whole separate 
dummy array for indices, but that does seem to be the only way with 
typcial sort routines.

I just went the brute-force way of modifying Oskar's sort routine to 
handle the case I need.

--bb