#include<bits/stdc++.h>

using namespace std;

typedef chrono::high_resolution_clock Clock_t;
typedef chrono::milliseconds     Time_scale_t;
 
int main() 
{
	ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	mt19937_64 random;
	
	for(int k = 15; k <= 22; k++)
	{
		size_t n = 1 << k; multiset<int> x; vector<int> a(n); 
		
		for(int i = 0; i < n; i++)
			x.insert(1+random()%100000);
		
		auto start_time  = Clock_t::now(); int j = 0;
		
		// copying the multiset x to vector a 
		
		for(auto b:x)
			a[j++] = b;
		
    	auto duration = Clock_t::now() - start_time;

		assert( is_sorted(a.begin(),a.end()) );
		
    	auto elapsed_time = chrono::duration_cast<Time_scale_t>(duration).count();

    	cout << "pow(2," << k << ") = " << n  << " items: " << elapsed_time << " msec\n";
	}
}