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

[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.

  • $\begingroup$ You can just sort by the second coordinate, and then sort by the first. If your sorting algorithm is stable (which it should be if implemented carefully), then you'll obtain the array of pairs sorted in lexicographical order, just like you wanted. $\endgroup$ – xavierm02 Jan 2 '17 at 14:04
  • 1
    $\begingroup$ I'm not sure I understand what you're asking. If the two sets have size $m$ and $n$, assuming any usual computational model, I'm not sure how you would hope to achieve a better complexity when the size of the output is $mn$. $\endgroup$ – quicksort Jan 2 '17 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.