#include <stdio.h>
#include <stdlib.h>


// randomized quicksort
template<typename T>
void quicksort (T a[], int n) {

  int i, j; T p, t;
  
  while (n > 10) {

    // choose pivot
    p = a[rand() % n];

    // partitioning

    i = -1; j = n;
    while (true) {

      while (a[++i] < p);
      while (p < a[--j]);

      if (i >= j) break;

      // swap

      t=a[i]; a[i]=a[j]; a[j]=t;
    }

    if (j != n-1) ++j;

    // now: a[0...j-1] <= p <= a[j..n-1]

    // recursively sort the smaller array, and iteratively the larger one

    if (j < n-j) {
      quicksort (a, j);

      a += j;
      n -= j;
    } else {

      quicksort (a+j, n-j);
      n = j;
    }
  }

  // insertion sort (for small instances)
  for (i=1; i<n; i++) {

    p = a[i];
    for (j=i; j>0 && p<a[j-1]; j--)

      a[j]=a[j-1];
    a[j] = p;
  }
}

// test
int main() {
  int A[100];
  for (int i=0; i<100; i++) A[i] = rand()%100;

  quicksort<int> (A, 100);  // sort numbers

  // output
  for (int i=0; i<100; i++) printf ("%i ", A[i]);

  printf ("\n");

  return 0;
}