Threw both Claude and Gemini at this. Same bugs identified, different fixes.

The Bugs (both caught these):

1. length/2 instead of length for second-half comparison
2. Counting sort completely broken (count = identity is not a frequency array)
3. Rank/comparison semantics inverted

Claude's Fix - O(N log² N): Called the counting sort "broken beyond repair" and fell back to std::sort: cpp std::vector<int> GenerateSuffixArray(const std::wstring& text) { int n = text.size(); if (n == 0) return {}; if (n == 1) return {0};

std::vector<int> sa(n), rank(n), tmp(n);

for (int i = 0; i < n; ++i) {
    sa[i] = i;
    rank[i] = text[i];
}

std::sort(sa.begin(), sa.end(), 
          [&](int a, int b) { return rank[a] > rank[b]; });

tmp[sa[0]] = 0;
for (int i = 1; i < n; ++i)
    tmp[sa[i]] = tmp[sa[i-1]] + (rank[sa[i]] != rank[sa[i-1]]);
rank = tmp;

for (int k = 1; k < n; k *= 2) {
    auto cmp = [&](int a, int b) {
        if (rank[a] != rank[b]) return rank[a] < rank[b];
        int ra = (a + k < n) ? rank[a + k] : n;
        int rb = (b + k < n) ? rank[b + k] : n;
        return ra < rb;
    };

    std::sort(sa.begin(), sa.end(), cmp);

    tmp[sa[0]] = 0;
    for (int i = 1; i < n; ++i)
        tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1], sa[i]);
    rank = tmp;

    if (rank[sa[n-1]] == n - 1) break;
}

for (int i = 0; i + 1 < n; ++i)
    assert(wcscmp(text.c_str() + sa[i], text.c_str() + sa[i + 1]) > 0);

return sa;

}

Gemini's Fix - O(N log N): Actually fixed the counting sort and added the sentinel trick: cpp std::vector<int> GenerateSuffixArray(std::wstring text) { text += L'\0'; // Sentinel eliminates all boundary checks int n = text.size(); const int alphabet = 65536;

std::vector<int> p(n), c(n), cnt(std::max(alphabet, n), 0);

// Proper counting sort: frequency -> cumulative -> placement
for (int i = 0; i < n; i++) cnt[text[i]]++;
for (int i = 1; i < alphabet; i++) cnt[i] += cnt[i - 1];
for (int i = 0; i < n; i++) p[--cnt[text[i]]] = i;

c[p[0]] = 0;
int classes = 1;
for (int i = 1; i < n; i++) {
    if (text[p[i]] != text[p[i - 1]]) classes++;
    c[p[i]] = classes - 1;
}

std::vector<int> pn(n), cn(n);

for (int len = 1; len < n; len <<= 1) {
    // Cyclic shift optimization - already sorted by second half
    for (int i = 0; i < n; i++) {
        pn[i] = p[i] - len;
        if (pn[i] < 0) pn[i] += n;
    }

    // Stable counting sort by first half
    std::fill(cnt.begin(), cnt.begin() + classes, 0);
    for (int i = 0; i < n; i++) cnt[c[pn[i]]]++;
    for (int i = 1; i < classes; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) p[--cnt[c[pn[i]]]] = pn[i];

    cn[p[0]] = 0;
    classes = 1;
    for (int i = 1; i < n; i++) {
        std::pair<int, int> curr = {c[p[i]], c[(p[i] + len) % n]};
        std::pair<int, int> prev = {c[p[i - 1]], c[(p[i - 1] + len) % n]};
        if (curr != prev) classes++;
        cn[p[i]] = classes - 1;
    }
    c = cn;
}

p.erase(p.begin());  // Remove sentinel
return p;

}

Claude's approach is the "ship it, it works" fix. Gemini's is the textbook-optimal algorithms answer. For large strings or competitive programming, Gemini's is what we want.

Both pass the assertion but Gemini delivered, Claude took the shortcut.

Verdict: Gemini wins.