# 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? Commented Feb 13, 2016 at 19:44
• Also what do you mean by "efficient"? You want the fewest operations? Fastest code? Shortest code? Commented Feb 13, 2016 at 19:45
• @march The result given by Gatherby[Sortedby[ ]].
– Shb
Commented Feb 13, 2016 at 19:47
• Check those results with a calculator, they are wrong! Commented Feb 13, 2016 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. Commented Feb 14, 2016 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
Commented Feb 13, 2016 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. Commented Feb 13, 2016 at 22:47
• f7 too returns the wrong results for the example list in the updated question.
– Shb
Commented Feb 13, 2016 at 23:04
• Thank you @Simon, I updated the post with your suggestions.
– kglr
Commented Feb 13, 2016 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
Commented Feb 13, 2016 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. Commented Feb 13, 2016 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 :) Commented Feb 13, 2016 at 21:10
• see updated question.
– Shb
Commented Feb 13, 2016 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]]] &]] Commented Feb 13, 2016 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
Commented Feb 13, 2016 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
Commented Feb 13, 2016 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
Commented Feb 13, 2016 at 20:19
• hmmm why is SortBy[list, Norm] giving me: {{1, 7}, {1, 3}, {3, 1}, {1, 6}, {1, 20}}
– Shb
Commented Feb 13, 2016 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. Commented Feb 13, 2016 at 21:10
• I am finished chasing a moving target. Commented Feb 14, 2016 at 1:53