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

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.

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

Bill Baxter wrote:
> 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 thought that should be easy with tuple parameters, but something that
i think is a bug stopped my litte test. see the attachment.
in line 11 the type of b is char[][] (as expected), but using it as such
gives an error. bummer...