bitonic sort

bitonic.cpp

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

void make_leq(int& a, int& b) {
  if (a > b) swap(a,b);
}

void bitonic(vector<int>& xs) {
  int n = xs.size();
  for (int i = 1; i < n; i <<= 1) {
    //cout << "iter = " << i << endl;
    //cout << "reversing" << endl;
    for (int item = 0; item < n/2; ++item) {
      int l = item/i*i*2, r = l + 2*i - 1, idx = i - 1 - item % i;
      int a = l + idx, b = r - idx;
      if (b >= n)
        break;
      //a = min(a, n-1);
      //b = min(b, n-1);
      //cout << "a b = " << a << " "<< b << endl;
      make_leq(xs[a], xs[b]);
    }
    for (int j = i/2; j >= 1; j >>= 1) {
      //cout << "j=" << j << endl;
      for (int item = 0; item < n/2; ++item) {
        int l = item/j*j*2, idx = item % j;
        int a = l + idx, b = l + j + idx;
        if (b >= n)
          break;
        //a = min(a, n - 1);
        //b = min(b, n - 1);
        //cout << "a b = " << a << " "<< b << endl;
        make_leq(xs[a], xs[b]);
      }
    }
  }
}

double get_time() {
  struct timezone tzp;
  timeval now;
  gettimeofday(&now, &tzp);
  return now.tv_sec + now.tv_usec / 1000000.;
}

int main() {
  /*
  for (int i = 0; i < 1000; ++i) {
    int n = rand() % 1000;
    vector<int> xs;
    for (int j = 0; j < n; ++j) xs.push_back(rand() % 1000);
    //for(int x: xs) cout << x<< " "; cout << endl;
    bitonic(xs);
    //for(int x: xs) cout << x<< " "; cout << endl;
    assert(is_sorted(begin(xs),end(xs)));
  }
  */
  vector<int> xs, ys;
  for (int j = 0; j < 10000000; ++j) xs.push_back(rand() % 1000);
  ys = xs;
  double t0 = get_time();
  sort(begin(xs),end(xs));
  double t1= get_time();
  bitonic(ys);
  double t2 = get_time();
  cout << (t1-t0) << " " << (t2-t1) << endl;
}