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 arraysorted_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 [a, b]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.
Leverege sorting by two fields from known sorting index(gather or scatter) of each field
algorithms;sorting