39
Sorting By PSP
•To sort, compute the position in the output by counting the number of elements smaller than
•
•
•
•
•
[1,1..n] begin
[1..n,1]   ST := S#[Index2,Index1]; -- Transpose input
            P := +<<[1..n,1..n](>>[*,1..n]S <= >>[1..n,*]ST);
-- Compare n^2 items, reduce
            S := S#[Index1,P]; -- Reorder by permutation
         end;
   3  1  4  5  9  2
3  1  0  1  1  1  0
1  1  1  1  1  1  1
4  0  0  1  1  1  0
5  0  0  0  1  1  0
9  0  0  0  0  1  0
2  1  0  1  1  1  1
P  
3 1 4 5 6 2
S  
3 1 4 5 9 2
ST
3
1
4
5
9
2
S  
1 2 3 4 5 9