1. fáze: každý prvek bi zařazovaného pole B[1..k] bude mít své vlákno, které ho zatřídí do stromu metodou Search (viz vzorový kód). Výsledkem bude pomocné pole C[1..k], obsahující pro každý prvek bi odkaz na list stromu, vlevo od něhož se má bi připojit.
2. fáze: potřebujeme nyní identifikovat všechny neprázdné řetězce B1, ..., Bm (jejich počet m předem neznáme), které se budou vkládat mezi listy stávajícího stromu. Na obr. 6.6 ve skriptech to vypadá jednoduše, ale uvědomte si, že algoritmus ty řetězce "nevidí." Musíme mu sdělit, kde v poli B začínají a končí. Začátek každého řetězce zjistíme jednoduše v poli C - je to pozice, jejíž obsah je odlišný od pozice předchozí. Sekvenčně by to byla hračka, ale my to musíme paralelizovat.
Proto vytvoříme pomocné binární pole D[1..k] s jedničkami na počátečních pozicích řetězců:
D[1]: = 1
for 2 ≤ i ≤ k pardo
if C[i -1] ≠ C[i] then D[i] := 1
else D[i] := 0
Následně spočteme prefixovou sumu pole D a výsledek uložíme do pole E. V prvcích pole E nyní máme očíslování jednotlivých řetězců B1, ..., Bm. Všimněte si, že jejich počet je m = E[k]. Konečně vytvoříme pole F[1..m+1], které bude obsahovat indexy začátků řetězců Bi v poli B:
F[1] := 1
for 2 ≤ i ≤ k pardo
if E[i -1] ≠ E[i] then F[E[i]] := i
F[m+1] := k+1
Každý řetězec Bi začíná na pozici F[i] a končí na pozici F[i+1]-1. Příklad pro k = 8, m = 4:
C:
| a1 | a2 | a2 | a2 | a5 | a5 | a9 | a9 |
D:
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 |
E:
| 1 | 2 | 2 | 2 | 3 | 3 | 4 | 4 |
F:
| 1 | 2 | 5 | 7 | 9 |
3. fáze: pro každý řetězec Bi se spustí samostatné vlákno, které ho bude zařazovat. Zamkne rodičovský uzel p listu ai , k němuž se Bi připojuje, a přidá k němu prostřední prvek Bi jako nový list. Pro každé ze dvou zbývajících neprázdných půlek Bi spustí samostatné vlákno, které se bude chovat analogicky, viz obr. 6.6 ve skriptech. Nyní se spustí metoda Balance, kterou lze myslím použít beze změny z jednoduché verze algoritmu. Stejně tak zamykání a odemykání rodičovského uzlu.
Oproti skriptům je implementace zjednodušená, není nutno synchronizovat jednotlivé vlny vyvážení stoupající stromem, stačí vždy zamknout a vyvážit jen uzel, ke kterému se navěšuje nový potomek.