After playing by hand with real data in the log 103. Fusion 2: the manual tinkering, I have a better grasp of what I'm dealing with, and how. The odd/even idea is interesting but in the end, the algorithm boils down to: "Is a semi-arc already output ?" and each new entry, with a pair of semi-arcs, can output nothing, one of the semi-arcs, or the fused pair. That's as simple as that.

Meanwhile, since not all semi-arcs pairs are fused, the rate of shrinking of the files is... lower than 50% per pass. But still probably more than 25%. This doubles the number of passes but that's still OK. I want the fusion program to be simple and efficient enough that it does not require crazy optimisations that will take ages to fine-tune, just so it could run a bit faster for a run that would take a few hours at most.

Anyway, the data show that most merges occur at the beginning of the list, the first entries have a much higher chance of being merged, and the last ones often linger... The idea to perform a pair of passes with sorts in increasing and decreasing directions looks good, in this light.

The RAM requirements are reasonable, since only 1 bit per semi-arc is necessary. 4Gi points require 512MiB for w32, so I'm good up to w36 with 16GiB installed. Each semi-arc is identified by its starting point so that's all that counts... A priori, no need of extra bonus flags with this new version.

But if the algo works well for for "maximal orbits", the behaviour is not yet clear for the weird cases of multiple orbits with various lengths. I'll have to test it for w5 for example!

---

So let's just do it.

By the way, w5 has 16 orbits, of lengths 4, 42 and 84.

sorted by src:
 0  1 1  1
 1 14 1 14
 2 28 1 14
 3  8 1  8
 4 21 1  6
 5  5 1 21
 6 16 1  8
 7 29 1 13
 8 22 1 10
 9 24 1  8
10 10 1 21
11 18 1 57
12 31 1  7
13 19 1 19
14 26 1 20
15 15 1 21
16 17 1  3
17  7 1 12
18  4 1 17
19 27 1  5
20 25 1 16
21 11 1  4
22  3 1 66
23  9 1 29
24  2 1  9
25 20 1  5
26 12 1 41
27  6 1 17
28 23 1 24
29 13 1  7
30 30 1 21
31  0 1  1

Sorted by dst:
31  0 1  1
 0  1 1  1
24  2 1  9
22  3 1 66
18  4 1 17
 5  5 1 21
27  6 1 17
17  7 1 12
 3  8 1  8
23  9 1 29
10 10 1 21
21 11 1  4
26 12 1 41
29 13 1  7
 1 14 1 14
15 15 1 21
 6 16 1  8
16 17 1  3
11 18 1 57
13 19 1 19
25 20 1  5
 4 21 1  6
 8 22 1 10
28 23 1 24
 9 24 1  8
20 25 1 16
14 26 1 20
19 27 1  5
 2 28 1 14
 7 29 1 13
30 30 1 21
12 31 1  7

side by side:
 0  1 1  1    31  0 1  1
 1 14 1 14     0  1 1  1
 2 28 1 14    24  2 1  9
 3  8 1  8    22  3 1 66
 4 21 1  6    18  4 1 17
 5  5 1 21     5  5 1 21
 6 16 1  8    27  6 1 17
 7 29 1 13    17  7 1 12
 8 22 1 10     3  8 1  8
 9 24 1  8    23  9 1 29
10 10 1 21    10 10 1 21
11 18 1 57    21 11 1  4
12 31 1  7    26 12 1 41
13 19 1 19    29 13 1  7
14 26 1 20     1 14 1 14
15 15 1 21    15 15 1 21
16 17 1  3     6 16 1  8
17  7 1 12    16 17 1  3
18  4 1 17    11 18 1 57
19 27 1  5    13 19 1 19
20 25 1 16    25 20 1  5
21 11 1  4     4 21 1  6
22  3 1 66     8 22 1 10
23  9 1 29    28 23 1 24
24  2 1  9     9 24 1  8
25 20 1  5    20 25 1 16
26 12 1 41    14 26 1 20
27  6 1 17    19 27 1  5
28 23 1 24     2 28 1 14
29 13 1  7     7 29 1 13
30 30 1 21    30 30 1 21
31  0 1  1    12 31 1  7

C'est parti.

Let's use a real scoreboard now, by the way:

0                 15                  31
|                 |                   |
.... .... .... .... .... .... .... ....

 0  1 1  1    31  0 1  1    =>  31 1 2 2
+... .... .... .... .... .... .... ...*

 1 14 1 14     0  1 1  1     =>   1 14 1 14
++.. .... .... .... .... .... .... ...*

 2 28 1 14    24  2 1  9   => 24 28 2 23
+++. .... .... .... .... .... *... ...*

 3  8 1  8    22  3 1 66  =>  22 8 2 74
++++ .... .... .... .... ..*. *... ...*

 4 21 1  6    18  4 1 17  => 18 21 2 23
++++ +... .... .... ..*. ..*. *... ...*

 5  5 1 21     5  5 1 21   => orbit closed ! len=21
++++ ++.. .... .... ..*. ..*. *... ...*

 6 16 1  8    27  6 1 17  =>  27 16  2 25
++++ +++. .... .... ..*. ..*. *..* ...*

 7 29 1 13    17  7 1 12   => 17 29 2 25
++++ ++++ .... .... .**. ..*. *..* ...*

 8 22 1 10     3  8 1  8  => 8 22 1 10  (3 already out)
++++ ++++ +... .... .**. ..*. *..* ...*

 9 24 1  8    23  9 1 29  =>  23 24 2 37
++++ ++++ ++.. .... .**. ..** *..* ...*

10 10 1 21    10 10 1 21  => Orbit closed ! len=21
++++ ++++ +++. .... .**. ..** *..* ...*

11 18 1 57    21 11 1  4  => 21  18 2 61
++++ ++++ ++++ .... .**. .*** *..* ...*

12 31 1  7    26 12 1 41  => 26 31  2 48
++++ ++++ ++++ +... .**. .*** *.** ...*

13 19 1 19    29 13 1  7  => 29 19 2 26
++++ ++++ ++++ ++.. .**. .*** *.** .*.*

14 26 1 20     1 14 1 14    =>  14 26 1 20  (1 already out)
++++ ++++ ++++ +++. .**. .*** *.** .*.*

15 15 1 21    15 15 1 21  => Orbit closed ! len=21
++++ ++++ ++++ ++++ .**. .*** *.** .*.*

16 17 1  3     6 16 1  8  =>  16 17 1 3 (6 already out)
++++ ++++ ++++ ++++ +**. .*** *.** .*.*

17  7 1 12    16 17 1  3   => nothing (both already out)
++++ ++++ ++++ ++++ +**. .*** *.** .*.*

18  4 1 17    11 18 1 57   => nothing (both already out)
++++ ++++ ++++ ++++ +**. .*** *.** .*.*

19 27 1  5    13 19 1 19   => 19 27 1  5  (13 already out)
++++ ++++ ++++ ++++ +**+ .*** *.** .*.*

20 25 1 16    25 20 1  5  => 25 25 2 21
++++ ++++ ++++ ++++ +**+ **** **** .*.*

21 11 1  4     4 21 1  6   => nothing (both already out)
++++ ++++ ++++ ++++ +**+ **** **** .*.*

22  3 1 66     8 22 1 10   => nothing (both already out)
++++ ++++ ++++ ++++ +**+ **** **** .*.*

23  9 1 29    28 23 1 24  =>  28 23 1 24 (23 already out)
++++ ++++ ++++ ++++ +**+ **** **** **.*

24  2 1  9     9 24 1  8   => nothing (both already out)
++++ ++++ ++++ ++++ +**+ **** **** **.*

25 20 1  5    20 25 1 16    => nothing (both already out)
++++ ++++ ++++ ++++ +**+ **** **** **.*

26 12 1 41    14 26 1 20    => nothing (both already out)
++++ ++++ ++++ ++++ +**+ **** **** **.*

27  6 1 17    19 27 1  5    => nothing (both already out)
++++ ++++ ++++ ++++ +**+ **** **** **.*

28 23 1 24     2 28 1 14    => nothing (both already out)
++++ ++++ ++++ ++++ +**+ **** **** **.*

29 13 1  7     7 29 1 13    => nothing (both already out)
++++ ++++ ++++ ++++ +**+ **** **** **.*

30 30 1 21    30 30 1 21   => Orbit closed ! len=21
++++ ++++ ++++ ++++ +**+ **** **** **+*

31  0 1  1    12 31 1  7    => nothing (both already out)
++++ ++++ ++++ ++++ +**+ **** **** **+*

And that's it, the scoreboard is full, 4 short orbits of len=21 are output/detected, and we get the following compacted list of 17 elements:

16 17 1  3
14 26 1 20
29 19 2 26
26 31 2 48
21 18 2 61
23 24 2 37
 8 22 1 10
17 29 2 25
27 16 2 25
18 21 2 23
22  8 2 74
24 28 2 23
 1 14 1 14
31  1 2  2
28 23 1 24
25 25 2 21
19 27 1  5

___________________________________________________________

2nd pass:

src:
 1 14 1 14
 8 22 1 10
14 26 1 20
16 17 1  3
17 29 2 25
18 21 2 23
19 27 1  5
21 18 2 61
22  8 2 74
23 24 2 37
24 28 2 23
25 25 2 21
26 31 2 48
27 16 2 25
28 23 1 24
29 19 2 26
31  1 2  2

dst:
31  1 2  2
22  8 2 74
 1 14 1 14
27 16 2 25
16 17 1  3
21 18 2 61
29 19 2 26
18 21 2 23
 8 22 1 10
28 23 1 24
23 24 2 37
25 25 2 21
14 26 1 20
19 27 1  5
24 28 2 23
17 29 2 25
26 31 2 48

side:
 1 14 1 14    31  1 2  2
 8 22 1 10    22  8 2 74
14 26 1 20     1 14 1 14
16 17 1  3    27 16 2 25
17 29 2 25    16 17 1  3
18 21 2 23    21 18 2 61
19 27 1  5    29 19 2 26
21 18 2 61    18 21 2 23
22  8 2 74     8 22 1 10
23 24 2 37    28 23 1 24
24 28 2 23    23 24 2 37
25 25 2 21    25 25 2 21
26 31 2 48    14 26 1 20
27 16 2 25    19 27 1  5
28 23 1 24    24 28 2 23
29 19 2 26    17 29 2 25
31  1 2  2    26 31 2 48

 And let's clear the scoreboard:

.... .... .... .... .... .... .... ....

 1 14 1 14    31  1 2  2 => 31 14 3 16
++.. .... .... .... .... .... .... ...*

 8 22 1 10    22  8 2 74  => 22 22 3 84
++++ ++++ +... .... .... ..*. .... ...*

14 26 1 20     1 14 1 14   => 14 26 1 20  (1 already out)
++++ ++++ ++++ +++. .... ..*. .... ...*

16 17 1  3    27 16 2 25  => 27 17 3 28
++++ ++++ ++++ ++++ +... ..*. ...* ...*

17 29 2 25    16 17 1  3   => 17 29 2 25  (16 already out)
++++ ++++ ++++ ++++ ++.. ..*. ...* ...*

18 21 2 23    21 18 2 61   => 21 21 4 84
++++ ++++ ++++ ++++ +++. .**. ...* ...*

19 27 1  5    29 19 2 26    => 29 27 3 31
++++ ++++ ++++ ++++ ++++ .**. ...* .*.*

21 18 2 61    18 21 2 23   => nothing (both already out)
++++ ++++ ++++ ++++ ++++ +**. ...* .*.*

22  8 2 74     8 22 1 10  => nothing (both already out)
++++ ++++ ++++ ++++ ++++ +**. ...* .*.*

23 24 2 37    28 23 1 24  => 28  24 3 61
++++ ++++ ++++ ++++ ++++ +**+ ...* **.*

24 28 2 23    23 24 2 37  => 24 28 2 23   (23 already out)
++++ ++++ ++++ ++++ ++++ +**+ +..* **.*

25 25 2 21    25 25 2 21  =>  Orbit closed ! len=21
++++ ++++ ++++ ++++ ++++ +**+ ++.* **.*

26 31 2 48    14 26 1 20  =>  26 31 2 48 (14 already out)
++++ ++++ ++++ ++++ ++++ +**+ +++* **.*

27 16 2 25    19 27 1  5  => nothing (both already out)
++++ ++++ ++++ ++++ ++++ +**+ +++* **.*

28 23 1 24    24 28 2 23  => nothing (both already out)
++++ ++++ ++++ ++++ ++++ +**+ +++* **.*

29 19 2 26    17 29 2 25  => nothing (both already out)
++++ ++++ ++++ ++++ ++++ +**+ +++* **.*

31  1 2  2    26 31 2 48  => nothing (both already out)
++++ ++++ ++++ ++++ ++++ +**+ +++* **+*

Voilà !

Result: 10 arcs

14 26 1 20
22 22 3 84
31 14 3 16
27 17 3 28
17 29 2 25
21 21 4 84
29 27 3 31
28 24 3 61
24 28 2 23
26 31 2 48

___________________________________________________________

3rd pass:

src:
14 26 1 20
17 29 2 25
21 21 4 84
22 22 3 84
24 28 2 23
26 31 2 48
27 17 3 28
28 24 3 61
29 27 3 31
31 14 3 16

dest:
31 14 3 16
27 17 3 28
21 21 4 84
22 22 3 84
28 24 3 61
14 26 1 20
29 27 3 31
24 28 2 23
17 29 2 25
26 31 2 48

side:
14 26 1 20    31 14 3 16
17 29 2 25    27 17 3 28
21 21 4 84    21 21 4 84
22 22 3 84    22 22 3 84
24 28 2 23    28 24 3 61
26 31 2 48    14 26 1 20
27 17 3 28    29 27 3 31
28 24 3 61    24 28 2 23
29 27 3 31    17 29 2 25
31 14 3 16    26 31 2 48

And reset the scoreboard:

.... .... .... .... .... .... .... ....

Let's go:

14 26 1 20    31 14 3 16  => 31 26 4 36
++++ ++++ ++++ +++. .... .... .... ...*

17 29 2 25    27 17 3 28  => 27 29 5 53
++++ ++++ ++++ ++++ ++.. .... ...* ...*

21 21 4 84    21 21 4 84  =>  Orbit closed ! len=84
++++ ++++ ++++ ++++ ++++ ++.. ...* ...*

22 22 3 84    22 22 3 84  =>  Orbit closed ! len=84
++++ ++++ ++++ ++++ ++++ +++. ...* ...*

24 28 2 23    28 24 3 61   =>  28 28 2 84
++++ ++++ ++++ ++++ ++++ ++++ +..* *..*

26 31 2 48    14 26 1 20  =>  26 31 2 48    (14 already out)
++++ ++++ ++++ ++++ ++++ ++++ +++* *..*

27 17 3 28    29 27 3 31  => 29 27 3 31  (27 already out)
++++ ++++ ++++ ++++ ++++ ++++ +++* *+.*

28 24 3 61    24 28 2 23  => nothing (both already out)
++++ ++++ ++++ ++++ ++++ ++++ +++* *+.*

29 27 3 31    17 29 2 25  => nothing (both already out)
++++ ++++ ++++ ++++ ++++ ++++ +++* *+.*

31 14 3 16    26 31 2 48  => nothing (both already out)
++++ ++++ ++++ ++++ ++++ ++++ +++* *++*

And we are left with 5 entries:

31 26 4 36
27 29 5 53
28 28 2 84
26 31 2 48
29 27 3 31

___________________________________________________________

4th pass:

src:
26 31 2 48
27 29 5 53
28 28 2 84
29 27 3 31
31 26 4 36
dst:
31 26 4 36
29 27 3 31
28 28 2 84
27 29 5 53
26 31 2 48
side:
26 31 2 48     31 26 4 36
27 29 5 53     29 27 3 31
28 28 2 84     28 28 2 84
29 27 3 31     27 29 5 53
31 26 4 36     26 31 2 48

And reset the scoreboard:

.... .... .... .... .... .... .... ....

Let's go:

26 31 2 48     31 26 4 36   => 31 31 6 84
++++ ++++ ++++ ++++ ++++ ++++ +++. ...*

27 29 5 53     29 27 3 31   => 29 29 8 84
++++ ++++ ++++ ++++ ++++ ++++ ++++ .*.*

28 28 2 84     28 28 2 84   =>  Orbit closed ! len=84
++++ ++++ ++++ ++++ ++++ ++++ ++++ +*.*

29 27 3 31     27 29 5 53   => nothing (both already out)
++++ ++++ ++++ ++++ ++++ ++++ ++++ +*.*

31 26 4 36     26 31 2 48   => nothing (both already out)
++++ ++++ ++++ ++++ ++++ ++++ ++++ +*+*

Result : 2 entries that will become "closed orbits" during the next step:

 31 31 6 84
 29 29 8 84

___________________________________________________________

Conclusion : the algorithm can't reach orbits that have no crossing.

I have found 5 orbits with len=84 as well as 5 orbits of len=21.

Total=525, which is 2 less than 527 so there would be 1 or 2 orbits at most that are not scanned and with no crossing.

The algorithm appears to be stable and simple.

On the scoreboard, I wrote '+' where the src.src is, and all the entries before: this is not tested by the scoreboard but with a simple comparison. The stars '*' are "written forward" randomly but half of them are read sequentially.

I'm not sure I need an extra buffer for the semi-arcs that are not fused.

Voilà.