GatherBy/SplitBy and Sort a list

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}], 
 TableHeadings -> {None, {"functions", "timings"}}]

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

Additional timings:

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

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

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

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

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  *)