quick_sort [median of three]

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

#define     rep(i,k,n)      for(int i=k;i<n;i++)
#define     fast            ios_base::sync_with_stdio(false);cin.tie(NULL)
#define     read            freopen("input.txt","r",stdin)
#define     write           freopen("output.txt","w",stdout)
#define     D(x)            cout << '>' << #x << ':' << x << endl
#define     DD(x,y)         cout << '>' << #x << ':' << x << ' ' << #y << ':' << y << endl
#define     DDD(x,y,z)      cout << '>' << #x << ':' << x << ' ' << #y << ':' << y << ' ' << #z << ':' << z << endl
#define     PI              acos(-1)
#define     MP(x, y)        make_pair(x, y)
#define     PB(x)           push_back(x)
#define     ALL(p)          p.begin(),p.end()
#define     CLR(p)          memset(p, 0, sizeof(p))
#define     MEM(a, b)       memset(a, (b), sizeof(a))
#define     ff              first
#define     ss              second
#define     sf              scanf
#define     pf              printf
#define     PII             pair<int, int>
#define     ll              long long int
#define     ull             unsigned long long int

inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void set_bit(int & n, int b) { n |= two(b); }
inline void unset_bit(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }

template < class T > inline T gcd(T a, T b) {while(b) { a %= b; swap(a, b); } return a;}
template < class T > inline T bigmod(T p, T e, T M){
    ll ret = 1;
    for(; e > 0; e >>= 1){ if(e & 1) ret = (ret * p) % M; p = (p * p) % M; }
    return (T)ret;
}
template < class T > inline T power(T a, T n) {
    if(n==0) return 1;
    if(n==1) return a;
    T R = power(a,n/2);
    return (n%2==0) ? R*R : R*a*R;
}

int fx4[] = {0, 0, -1, +1};
int fy4[] = {+1, -1, 0, 0};
int fx8[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
int fy8[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
int fx8Knight[] = {+2, +2, +1, -1, -2, -2, -1, +1};
int fy8Knight[] = {+1, -1, -2, -2, -1, +1, +2, +2};

int cnt = 0;

int median(int *a, int low, int high)
{
    int midIndex = low + (high - low) / 2;
    int leftVal = a[low], rightVal = a[high - 1], midVal = a[midIndex];
    int pidx = low;
    int pivot = leftVal;
    if((midVal > pivot && midVal < rightVal) || (midVal > rightVal && midVal < pivot))
    {
        pivot = midVal;
        pidx = midIndex;
    }
    else if((rightVal > pivot && rightVal < midVal) || (rightVal > midVal && rightVal < pivot))
    {
        pivot = rightVal;
        pidx = high - 1;
    }
    return pidx;
}

int Partition(int *a, int low, int high)
{
    int pidx = median(a, low, high);
    int pivot = a[pidx];
    int i = low-1;
    int j = high;
    while(i<j)
    {
        do
        {
            i++;
            cnt++;
        } while(a[i]<=pivot && i <= high);
        do
        {
            j--;
            cnt++;
        }while(a[j]>pivot && j >= low);
        if(i<j) swap(a[i],a[j]);
    }
    swap(a[pidx],a[j]);
    return j;
}

void QuickSort(int *a, int low, int high)
{
    int pindex;
    if(low < high)
    {
        pindex = Partition(a, low, high);
        DD(pindex,cnt);
        QuickSort(a, low, pindex);
        QuickSort(a, pindex+1, high);
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    read;
    write;
#endif
    fast;
    int n;
    while(cin>>n)
    {
        if(n==0) break;
        int arr[n];
        for(int i=0; i<n; i++) cin>>arr[i];
        QuickSort(arr,0,n);
        cout<<arr[0];
        for(int i=1; i<n; i++) cout<<" "<<arr[i];
        cout<<endl;
    }
    return 0;
}

/*
input:
10
10 20 30 40 50 60 70 80 90 100
0
*/