A little context. First of all gather index in my case contains position to sorted an array. For example for an array
array = [3, 2, 0, 1]
gather index will be
gather_index = [2, 3, 1, 0]
the following operation will produce sorted array
sorted_array[i] = array[gather_index[i]]
I need to do a sort by all pairs of fields in a cartesian product and apply some logic then. More precisely if the first set contains fields
and the second
[c, d, e]
Data should be sorted 6 times by
[(a, c), (a, d), (a, e), (b, c), (b, d), (b, e)]
that operation has O(N*M) complexity(N,M sizes of sets not a sorted array).
I'm curious can we somehow reduce it to O(N+M) or anything less than O(N*M) by using gather(or scatter) sorting index? First sort data by each fields to get indexes. Then use it to get data sorted by two fields.
Let's say array is a matrix with a few columns(a, b, c, etc). My question can be rephrase like Can I sort it by a_and_b in a cheaper way than just sort by two columns directly if I already know gather index(sorting index) that sort by 'a' and 'b' separately.