# GatherBy/SplitBy and Sort a list

So let's say I want to group a list of points based on their distance from the origin. I would do something like:

list = {{1, 20}, {1, 6}, {1, 7}, {1, 3}, {3, 1}};
gathered = GatherBy[list, Norm[#]&]


and that would give me what I need, but that would not necessarily respect the ordering. I can apply SortBy[] first and then GatherBy[] the result:

sorted = SortBy[list, Norm[#] &]
partitionedBy = GatherBy[sorted, Norm[#] &]


But that is not very efficient. Is there any more efficient way of doing this using Mathematica's built-in functions. If not, What would be the most efficient way of achieving this?

update: if list is set to be a reduced accuracy version of an exact numerical expression, some of the methods suggested below will yield incorrect results. That is investigated in this question.

• What would be your expected output for your example? – march Feb 13 '16 at 19:44
• Also what do you mean by "efficient"? You want the fewest operations? Fastest code? Shortest code? – Quantum_Oli Feb 13 '16 at 19:45
• @march The result given by Gatherby[Sortedby[ ]]. – Shb Feb 13 '16 at 19:47
• Check those results with a calculator, they are wrong! – Simon Woods Feb 13 '16 at 23:38
• The issue of how N affects Accuracy is a quite different problem to the original question regarding efficient sort & gather algorithms. It should be a separate question. People took time and trouble to answer the original question, and it's rather unfair to claim that their (perfectly good) answers don't work because of special features in your data that you didn't reveal until several hours later. It will also be more useful to future visitors looking for efficient sort & gather algorithms if the question is unencumbered by the requirement to avoid using N. – Simon Woods Feb 14 '16 at 11:41

As noted by @SimonWoods in the comments, using #.#& instead of Norm gives a huge speed up.

ClearAll[f1, f1b, f2, f2b, f3, f3b, f4, f5, f6, f7, f8]
f1 = GatherBy[SortBy[#, N@Norm@# &], N@Norm@# &] &;
f2 = SplitBy[SortBy[#, N@Norm@# &], N@Norm@# &] &;
f3 = SortBy[GatherBy[#, N[Norm@#] &], N[Norm[#[[1]]]] &] &;
f1b = GatherBy[SortBy[#, #.# &], #.# &] &;
f2b = SplitBy[SortBy[#, #.# &], #.# &] &;
f3b = SortBy[GatherBy[#, #.# &], #[[1]].#[[1]] &] &;
f4 = With[{norms = #.# & /@ #, lst = #},
lst[[#]] & /@ SplitBy[Ordering[norms], norms[[#]] &]] &;
f5 = With[{norms = #.# & /@ #, lst = #},
lst[[#]] & /@ GatherBy[Ordering[norms], norms[[#]] &]] &;
f6 = With[{gathered = GatherBy[#, #.# &]},
gathered[[Ordering[#.# & /@ (First /@ gathered)]]]] &;
f7 = With[{gathered = GatherBy[#, #.# &]},
With[{norms = #.# & /@ (First /@ gathered)},
gathered[[Ordering[norms]]]]] &;

list0 = RandomInteger[{0, 20}, {100000, 2}];
timings =
First[AbsoluteTiming[# = #2@list0;]] & @@@
Transpose[{{l1, l1b, l2, l2b, l3, l3b, l4, l5, l6, l7}, {f1, f1b,
f2, f2b, f3, f3b, f4, f5, f6, f7}}];
functions = {"f1", "f1b", "f2", "f2b", "f3", "f3b", "f4", "f5", "f6",
"f7"};
TableForm[Transpose[{functions, timings}],


Equal @@ ((Norm /@ (First /@ #) & /@ {l1, l1b, l2, l2b, l3, l3b, l4, l5, l6, l7}))
(* True *)


list0 = RandomInteger[{0, 500}, {100000, 2}];


list0 = RandomInteger[{0, 20}, {100000, 5}];


• Thanks. FYI, I just tested these with {{0.*10^-2, 0.*10^-2}, {1.3, 1.}, {0.2, 0.6}, {0.2, -0.6}, {1.3, -1.}, {-0.5, 1.5}, {-0.5, 0.4}, {0.6, 0.*10^-2}, {-1.6, 0.*10^-2}, {-0.5, -0.4}, {-0.5, -1.5}} and only f2 and f4 are giving me the results I am expecting. – Shb Feb 13 '16 at 22:40
• The difference between using Norm and #.#& accounts for a lot of the speed differences. It would be interesting to compare the different approaches using the same norm function throughout. – Simon Woods Feb 13 '16 at 22:47
• f7 too returns the wrong results for the example list in the updated question. – Shb Feb 13 '16 at 23:04
• Thank you @Simon, I updated the post with your suggestions. – kglr Feb 13 '16 at 23:09
• @Shb, the only difference between the outputs of the 10 functions is the ordering within each group; groups are ordered correctly. – kglr Feb 13 '16 at 23:15

This is more than 50% faster, since it evaluates only one Norm for each sublist:

AbsoluteTiming[list3 = SortBy[GatherBy[list, Norm], N[Norm[#[[1]]]] &];]

• I had result = With[{n = #.# &}, list~GatherBy~n~SortBy~n@*First] - same principle but faster if list is integers. – Simon Woods Feb 13 '16 at 21:08
• @SimonWoods Can't try it as it is, because V9 still here, but Norm is usually a slow thing, so I guess you're right :) – Dr. belisarius Feb 13 '16 at 21:10
• see updated question. – Shb Feb 13 '16 at 22:09
• @Shb The only difference is the order into the sublists list2 = {{0.*10^-2, 0.*10^-2}, {1.3, 1.}, {0.2, 0.6}, {0.2, -0.6}, {1.3, -1.}, {-0.5, 1.5}, {-0.5, 0.4}, {0.6, 0.*10^-2}, {-1.6, 0.*10^-2}, {-0.5, -0.4}, {-0.5, -1.5}}; Sort /@ SplitBy[SortBy[list2, Norm], Norm] == Sort /@ SortBy[GatherBy[list2, Norm], N[Norm[#[[1]]] &]] – Dr. belisarius Feb 13 '16 at 22:17
• I don;t understand why you have an additional sort in there, but no your new suggestion too returns the old wrong answer. – Shb Feb 13 '16 at 22:29
list = RandomInteger[{0, 20}, {10000, 2}];

AbsoluteTiming[list2 = GatherBy[SortBy[list, N[Norm[#]] &], Norm];]

(*  {0.149292, Null}  *)


SplitBy will partition without additional sorting; however, it is nonetheless slower.

AbsoluteTiming[list3 = SplitBy[SortBy[list, N[Norm[#]] &], Norm];]

(*  {0.212032, Null}  *)


Verifiying that the two results are identical

list2 === list3

(*  True  *)


Sort and SortBy sort by canonical order. This is only equivalent to numeric order for numbers rather than numeric expressions. See Possible Issues under Sort: "Numeric expressions are sorted by structure as well as numerical value"

EDIT: To address the revised question

list4 = {{0.*10^-2, 0.*10^-2}, {1.3, 1.}, {0.2,
0.6}, {0.2, -0.6}, {1.3, -1.}, {-0.5, 1.5}, {-0.5, 0.4}, {0.6,
0.*10^-2}, {-1.6, 0.*10^-2}, {-0.5, -0.4}, {-0.5, -1.5}};

ans1 = GatherBy[SortBy[list4, N[Norm[#] &]], Norm];


Since you are using machine numbers in this case, use of N is not required

ans2 = GatherBy[SortBy[list4, Norm], Norm];

ans3 = SplitBy[SortBy[list4, N[Norm[#]] &], Norm];


Again, since you are using machine numbers, use of N is not required

ans4 = SplitBy[SortBy[list4, N[Norm[#]] &], Norm];


These are all identical

ans1 === ans2 === ans3 === ans4

(*  True  *)


These are in the correct numeric order

OrderedQ[Norm[#[[1]]] & /@ ans1]

(*  True  *)

• I just noticed that GatherBy[SortBy[list, Norm], Norm] does not give the answer I was expecting. it gives me: {{{1, 7}}, {{1, 3}, {3, 1}}, {{1, 6}}, {{1, 20}}} I was expecting {{1,3},{3,1}} to come first. Also there is extra parenthesis. – Shb Feb 13 '16 at 20:17
• I initially had: SortBy[GatherBy[list, Norm], Norm] but I realized that while it was giving me the right answer, it was only working because Norm[list]==Norm[{list}] which doesn't necessarily hold for a given function. – Shb Feb 13 '16 at 20:19
• hmmm why is SortBy[list, Norm] giving me: {{1, 7}, {1, 3}, {3, 1}, {1, 6}, {1, 20}} – Shb Feb 13 '16 at 20:20
• I suggest using #.#& in place of N@*Norm for integers - it omits the square root step but that doesn't change the ordering. – Simon Woods Feb 13 '16 at 21:10
• I am finished chasing a moving target. – Bob Hanlon Feb 14 '16 at 1:53