linsort - 3
Lin / Devi
Binary-tree abstraction for any comparison sort.
Represents comparisons made by
a specific sorting algorithm
on inputs of a given size.
Abstracts away everything else – control and data movement – counting only comparisons.
Each internal node is annotated by i:j, which are indices of array elements from their original positions.
Each leaf is annotated by a permutation (1), (2), …, (n) of orders that the algorithm determines.