The loop runs log n rounds and the version here calls a comparison sort inside each one, which is O(n log^2 n). Both halves of the key are ranks smaller than n, so a two-pass radix sort - by the second element, then a stable pass by the first - sorts a round in O(n) and brings the total to O(n log n). Genuinely linear constructions exist as well: DC3 from Karkkainen and Sanders, and SA-IS from Nong, Zhang and Chan, whose induced sorting is what Chromium ships in Zucchini. Linear does not mean fastest, though: libdivsufsort, the sorter most production code reaches for, is O(n log n) in the worst case and still beats the linear methods on real inputs. Doubling is still worth knowing because the rank array it produces on the way is the inverse suffix array, which Kasai's LCP algorithm and many string problems need anyway.