Multikey quicksortとかTernary quicksortとか呼ばれるやつ．（参考： 続・アルゴリズムを学ぼう　4.7 接尾辞配列(SuffixArray)）

multikey_quick_sort.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <assert.h>

using namespace std;

// pivotを選ぶ．
char find_pivot_char(vector<string> &data, int left, int right, int depth) {
    assert(0 <= left);
    assert(right <= data.size());
    assert(left + 1 <= right);

    char a = data[left].size() <= depth ? -1 : data[left][depth];
    char b = data[(left + right) / 2].size() <= depth ? -1 : data[(left + right) / 2][depth];
    char c = data[right - 1].size() <= depth ? -1 : data[right - 1][depth];

	// a, b, cの真ん中
    vector<char> v = { a, b, c };
    sort(v.begin(), v.end());
    return v[1];
}

void multikey_quick_sort(vector<string> &data, int left, int right, int depth) {
    assert(0 <= left);
    assert(right <= data.size());

    // ソートする必要ない
    if (right - left <= 1) {
        return;
    }

    char pivot = find_pivot_char(data, left, right, depth);
    int left_pivot_idx = left, l = left;
    int right_pivot_idx = right - 1, r = right - 1;

    // [pivotと同じ文字，pivotより小さい文字，pivotより大きい文字，pivotと同じ文字]となるようにdataをソートする
    while (true) {

        // pivotより大きい文字を探す
        while (l <= r) {
            char k = data[l].size() <= depth ? -1 : data[l][depth];    
            if (k > pivot) {
                break;
            }
            // pivotと同じ文字は右に集める
            else if (k == pivot) {
                swap(data[left_pivot_idx++], data[l]);
            }
            l++;
        }

        // pivotより小さい文字を探す
        while (l <= r) {
            char k = data[r].size() <= depth ? -1 : data[r][depth];
            if (k < pivot) {
                break;
            }
            // pivotと同じ文字は左に集める
            else if (k == pivot) {
                swap(data[right_pivot_idx--], data[r]);
            }
            r--;
        }

        if (l > r) {
            break;
        }

        // 左側のpivotより大きい文字と右側のpivotより小さい文字を交換
        swap(data[l++], data[r--]);
    }

    // [pivotより小さい文字，pivotと同じ文字，pivotより大きい文字]となるようにソートする
    // 左側にあるpivotと同じ文字を真ん中に集める
    int left_swap_size = min(left_pivot_idx - left, l - left_pivot_idx);
    for (int i = 0; i < left_swap_size; ++i) {
        swap(data[left + i], data[r - i]);
    }
    left_pivot_idx = left + (l - left_pivot_idx);

    // 右側にあるpivotと同じ文字を真ん中に集める
    int right_swap_size = min(right - right_pivot_idx - 1, right_pivot_idx - r);
    for (int i = 0; i < right_swap_size; ++i) {
        swap(data[right - i - 1], data[l + i]);
    }
    right_pivot_idx = right - (right_pivot_idx - r);

    // ソート
    multikey_quick_sort(data, left, left_pivot_idx, depth);   // 左
    multikey_quick_sort(data, right_pivot_idx, right, depth); // 右
    if ((right_pivot_idx - left_pivot_idx != right - left) || (data[left].size() >= depth)) {
        multikey_quick_sort(data, left_pivot_idx, right_pivot_idx, depth + 1);  // 真ん中
    }
}

void multikey_quick_sort(vector<string> &data) {
    multikey_quick_sort(data, 0, data.size(), 0);
}

void main() {
    vector<string> v = { "banana", "anana", "nana", "ana", "na", "a" };
    multikey_quick_sort(v);

    for (string s : v) {
        cout << s << endl;
    }
}