list={{0,...},{1,...},{1,...},{0,...},{3,...},{3,...},{0,...},{0,...},{5,...},{5,...},{5,...},{0,...},{5,...},{0,...},...}

list[[All,1]]
(* {0,1,1,0,3,3,0,0,5,5,5,0,5,0,...} *)

{0,1,1,0,3,3,0,0,5,5,5,5,0,0,...}

3, 1, 5, 4, 6, ...

sortedPositions[list_List] :=
  Module[{tmp = list[[All, 1]], length, pos, tmp1, tmp2,
    tmp3},
   length = Length[tmp];
   tmp1 = List /@ Cases[Transpose[{tmp, Range[length]}], {0, _}];
   tmp2 = DeleteCases[Transpose[{tmp, Range[length]}], {0, _}];
   tmp3 = GatherBy[tmp2, First];
   tmp2 = Join[tmp1, tmp3];
   Flatten[SortBy[tmp2, #[[1, 2]] &], 1][[All, 2]]
   ];

num = 20;
testList = Join[List /@ RandomInteger[{0, 9}, num], RandomReal[{0, 1}, {num, 6}], 2]

(*
{{6,0.456203,0.0900917,0.62677,0.638615,0.227849,0.61252},
{4,0.317069,0.44889,0.456945,0.05121,0.940742,0.495415},
{7,0.573698,0.381817,0.859495,0.517238,0.459022,0.957771},
{5,0.832945,0.867634,0.0843833,0.296803,0.944986,0.563913},
{1,0.598743,0.803861,0.082542,0.138926,0.630364,0.0445202},
{7,0.289183,0.257115,0.358083,0.677393,0.206347,0.987678},
{5,0.947487,0.320408,0.600928,0.0718489,0.976703,0.449376},
{0,0.0996927,0.210278,0.408291,0.861885,0.946081,0.0522955},
{0,0.537572,0.160541,0.212737,0.508406,0.353786,0.479605},
{7,0.0815373,0.0677839,0.388955,0.681041,0.795607,0.404398},
{4,0.18704,0.253819,0.141732,0.43889,0.931269,0.556534},
{2,0.262136,0.110553,0.60296,0.482498,0.693049,0.430039},
{5,0.569696,0.262133,0.397575,0.246202,0.499777,0.073326},
{6,0.487893,0.121165,0.413376,0.874849,0.836484,0.792685},
{0,0.677934,0.543956,0.593967,0.138832,0.896184,0.604194},
{2,0.138691,0.150235,0.614355,0.326924,0.615902,0.900494},
{0,0.0254698,0.258354,0.377134,0.569083,0.0925844,0.672802},
{7,0.354392,0.976598,0.658138,0.124943,0.39485,0.239671},
{2,0.622461,0.195612,0.997663,0.421797,0.130802,0.110463},
{2,0.136431,0.799215,0.698071,0.0599957,0.452992,0.378609}} *)

positions = sortedPositions[testList]
(* {1, 14, 2, 11, 3, 6, 10, 18, 4, 7, 13, 5, 8, 9, 12, 16, 19, 20, 15,
17} *)

testList[[positions]]
(*
{{6,0.456203,0.0900917,0.62677,0.638615,0.227849,0.61252},
{6,0.487893,0.121165,0.413376,0.874849,0.836484,0.792685},
{4,0.317069,0.44889,0.456945,0.05121,0.940742,0.495415},
{4,0.18704,0.253819,0.141732,0.43889,0.931269,0.556534},
{7,0.573698,0.381817,0.859495,0.517238,0.459022,0.957771},
{7,0.289183,0.257115,0.358083,0.677393,0.206347,0.987678},
{7,0.0815373,0.0677839,0.388955,0.681041,0.795607,0.404398},
{7,0.354392,0.976598,0.658138,0.124943,0.39485,0.239671},
{5,0.832945,0.867634,0.0843833,0.296803,0.944986,0.563913},
{5,0.947487,0.320408,0.600928,0.0718489,0.976703,0.449376},
{5,0.569696,0.262133,0.397575,0.246202,0.499777,0.073326},
{1,0.598743,0.803861,0.082542,0.138926,0.630364,0.0445202},
{0,0.0996927,0.210278,0.408291,0.861885,0.946081,0.0522955},
{0,0.537572,0.160541,0.212737,0.508406,0.353786,0.479605},
{2,0.262136,0.110553,0.60296,0.482498,0.693049,0.430039},
{2,0.138691,0.150235,0.614355,0.326924,0.615902,0.900494},
{2,0.622461,0.195612,0.997663,0.421797,0.130802,0.110463},
{2,0.136431,0.799215,0.698071,0.0599957,0.452992,0.378609},
{0,0.677934,0.543956,0.593967,0.138832,0.896184,0.604194},
{0,0.0254698,0.258354,0.377134,0.569083,0.0925844,0.672802}}
 *)

group2[lst_] :=
  Module[{x, i = 1}, Join @@ GatherBy[lst, #[[1]] /. 0 :> x[i++] &]]

big = RandomInteger[5, {10000, 3}];

Table[group[big] // Timing // First, {5}]

Table[group2[big] // Timing // First, {5}]

group[lst_] := Join @@ GatherBy[lst, #[[1]] /. 0 :> Unique[] &]

Join[List /@ RandomInteger[{0, 5}, 20], RandomReal[{0, 1}, {20, 6}], 2];

%[[All, 1]]

group[%%][[All, 1]]

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

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

list = {0, 1, 1, 0, 3, 3, 0, 0, 5, 5, 5, 0, 5, 0, 1};
Split[list] //. {h___, x : {a_, ___}, m___, y : {a_, ___}, t___} :>
    {h, x ~Join~ y, m, t} /; a =!= 0 // Flatten

(* {0, 1, 1, 1, 0, 3, 3, 0, 0, 5, 5, 5, 5, 0, 0} *)

list={{1,a},{1,b},{0,c},{2,d},{0,e},{2,f},{0,g},{4,h},{0,j}}

strangeSort[list_]:=Module[{r},
r=Split[list,#1[[1]]==0&];
r=GatherBy[r,#[[-1,1]]&];
r={#[[1]],Reverse@SortBy[Flatten[#[[2;;-1]],1],#[[1]]]}&/@r;
r=Flatten[r,2]]

strangeSort[list]

{{1,a},{1,b},{0,c},{2,d},{2,f},{0,e},{0,g},{4,h},{0,j}}

GatherByList[list_, representatives_] := Module[{func},
    func /: Map[func, _] := representatives;
    GatherBy[list, func]
]

g[list_] := Module[{max = Max @ list[[All, 1]] + 1},
    Join @@ GatherByList[list, Replace[list[[All, 1]], 0 :> max++, {1}]]
]

list = RandomInteger[5, {10^5, 3}];

r1 = g[list]; //AbsoluteTiming
r2 = group2[list]; //AbsoluteTiming

r1 === r2