Fairly often I have a need to get the Ordering of an expression but with recognition of duplicates. For example:

Ordering[{0, 4, 1, 1, 2}]
{1, 3, 4, 5, 2}

but with duplicates such as 3, 4 marked, i.e.:

{{1}, {3, 4}, {5}, {2}}

I have been using a decorate-and-sort followed by GatherBy and Part:

{0, 4, 1, 1, 2} //
  GatherBy[Sort[{#, Range@Length@#}\[Transpose]], First][[All, All, 2]] &
{{1}, {3, 4}, {5}, {2}}

Is there a better way?


1 Answer 1


Yes, there is!

Szabolcs showed a use of GatherBy in an inverted fashion as a substitute for a conventional decorate-and-sort. It proved both syntactically and computationally efficient.

By using that method in place of the decorate-and-sort in this application we can use Ordering directly, and also eliminate Part which was needed to strip the decoration:

myOrdering[a_] := GatherBy[Ordering @ a, a[[#]] &]

{0, 4, 1, 1, 2} // myOrdering
{{1}, {3, 4}, {5}, {2}}

This is nearly twice as fast as my old method in the question, and much shorter.

I hope this function proves to be as useful to others as I know it will be to me.

Related posts: (21453), (29551)

Applying Carl Woll's revealing method from GatherByList to this problem we get:

myOrdering2[a_] :=
  Module[{f, o = Ordering @ a},
    f /: f /@ _ = a[[o]];
    GatherBy[o, f]

This can be significantly faster in cases with heavy duplication:

big = RandomInteger[100, 1*^6];

r1 = myOrdering[big];  // RepeatedTiming // First
r2 = myOrdering2[big]; // RepeatedTiming // First

r1 === r2


  • $\begingroup$ So, looks like you've set the goal to get the most out of this method :-). +1, of course. $\endgroup$ Mar 16, 2013 at 13:43
  • 1
    $\begingroup$ @Leonid As soon as I saw that it was fast I realized it was going to impact a number of applications. This is an operation for which I've been carting old code around without much thought. It's nice to finally get a clean and fast function for it. $\endgroup$
    – Mr.Wizard
    Mar 16, 2013 at 13:49
  • $\begingroup$ Yes, I agree. Just wondering why I did not discover that myself, since I had lots of similar problems too. I think that somehow I was sure the performance would be much worse, so I did not even bother trying. A big mistake, it turns out. $\endgroup$ Mar 16, 2013 at 13:52
  • $\begingroup$ @Leonid Likewise, as I explained here. $\endgroup$
    – Mr.Wizard
    Mar 16, 2013 at 13:57
  • 2
    $\begingroup$ If I ever become a dairy farmer, I'm hiring you to milk my cows :P $\endgroup$
    – rm -rf
    Mar 16, 2013 at 16:15

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.