Fig. 1
From: Fast, parallel, and cache-friendly suffix array construction
Overview of caps-sa. In the first step of the algorithm the input text \(T\) is partition evenly across \(p\) partitions. Then each partition is sorted, pivots are sampled using the sampling routine, and located within each partition to create sub-partitions. Subsequently each sub-partition is collated. Finally the merge routine is used to complete the suffix and the LCP-array construction