#include "hwy/contrib/sort/algo-inl.h"
#include "hwy/contrib/sort/vqsort.h"

long long ticks(void)
{
  unsigned long long result;
  asm volatile(".byte 15;.byte 49;shlq $32,%%rdx;orq %%rdx,%%rax"
    : "=a"(result) :: "%rdx");
  return result;
}

#define N 131072
#define TIMINGS 127

int32_t r[N] __attribute__((aligned(4096)));
int32_t x[(TIMINGS+1)*N] __attribute__((aligned(4096)));
int32_t y[N] __attribute__((aligned(4096)));

long long t[TIMINGS+1] __attribute__((aligned(4096)));

int main()
{
  auto s = hwy::Sorter();
  hwy::SortAscending order;

  for (long long n = 1;n <= N;n += 1+(n/16)) {
    for (long long i = 0;i < n;++i)
      r[i] = random();
    for (long long j = 0;j <= TIMINGS;++j)
      for (long long i = 0;i < n;++i)
        x[j*n+i] = r[i];
    for (long long j = 0;j <= TIMINGS;++j)
      t[j] = ticks();

    for (long long j = 0;j <= TIMINGS;++j) {
      t[j] = ticks();
      s(x+j*n,n,order);
    }

    for (long long i = 0;i < n;++i)
      y[i] = r[i];
    std::sort(y,y+n);
    for (long long j = 0;j <= TIMINGS;++j)
      for (long long i = 0;i < n;++i)
        assert(y[i] == x[j*n+i]);

    for (long long i = 0;i < TIMINGS;++i)
      t[i] = t[i+1]-t[i];
    std::sort(t,t+TIMINGS);

    printf("%lld %lld %lld %lld\n",n,t[TIMINGS/4],t[TIMINGS/2],t[(3*TIMINGS)/4]);
  }
  return 0;
}