ponowne odkrycie binary insertion sort na psf

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>


using namespace std;

class timer{
    chrono::time_point<chrono::high_resolution_clock> a,b;
public:
    void start(){a = chrono::high_resolution_clock::now();}
    void stop() {b = chrono::high_resolution_clock::now();}
    double value(){
        chrono::duration<double> elapsed_seconds = b-a;
        return elapsed_seconds.count();
    }
    void show(){
        cout << value()<<" s"<<endl;
    }
};
mt19937 r;


string losowe_slowo(){
    uniform_int_distribution<int> gen_dl(4,15);
    uniform_int_distribution<int> gen_c(0,'z'-'a');
    string s="";
    generate_n(back_inserter(s),gen_dl(r), [&](){ return (char)'a'+gen_c(r); });
    return s;
}

void generuj (vector<string> &tab, size_t n){
    tab.clear();
    generate_n(back_inserter(tab),n, losowe_slowo);
}

void test1(vector<string> tab){
    timer stoper;

    stoper.start();
    sort(begin(tab), end(tab));
    stoper.stop();
    cout<<"posortowal qsortem w "<<stoper.value()<<"s\n";
    if (!is_sorted(begin(tab), end(tab)))
        cout<<"SORTOWANIE SPARTOLONO"<<endl;
}

void test2(vector<string> tab){
    timer stoper;

    vector<string> tab_out;
    tab_out.reserve(tab.size()); //dajemy fory tej metodzie

    stoper.start();

    for (auto v: tab){
        tab_out.insert( lower_bound(begin(tab_out),end(tab_out),v),v );
    }
    stoper.stop();
    cout<<"posortowal BIStem w "<<stoper.value()<<"s\n";
    if (!is_sorted(begin(tab_out), end(tab_out)))
        cout<<"SORTOWANIE SPARTOLONO"<<endl;
}


int main(){
    r.seed(1000500);

    vector <string> tab;

    for (int i=100;i<1000000; i*=10 ){
        generuj(tab,i);
        cout<<"Sortuj "<<i<<" wyrazow"<<endl;
        test1(tab); //tablica przekazywana jako kopia
        test2(tab);
        cout<<endl;
    }
    return 0;
}