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

int a[1000001],n;
int b[1000001],tmp[1000001];

int GetMax(int a[],int n)
{
    int max=a[0];
    for(int i=1;i<n;i++){
        if(a[i]>max)   max = a[i];
    }
    return max;
}


void QuickSort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
       if (i < j) swap(q[i], q[j]);
    }
    QuickSort(q, l, j), QuickSort(q, j + 1, r);
}

int ans;
void MergeSort(int q[],int l,int r)
{
    if(l==r)return;
    int i=l,mid=(l+r)/2,j=mid+1,k=l;

    MergeSort(q,l,mid);
    MergeSort(q,mid+1,r);

    while(i<=mid&&j<=r)
    {
       if(q[i]<=q[j]){
            tmp[k++]=q[i++];
       }
       else{
            ans=ans+j-k;
            tmp[k++]=q[j++];
        }
        }
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    for(int i=l;i<=r;i++)
        q[i]=tmp[i];
}

void MergeFindSort( int a[] , int n )
{
    int low , high , mid ;
    int temp ;
    for ( int i=1 ; i<n ; i++ )
    {
        temp = a[i ];
        low = 0 ;
        high = i - 1 ;
        while ( low <= high )
        {
            mid = ( low + high ) / 2 ;
            if ( a[mid] > temp )
                high = mid - 1 ;
            else
                low = mid + 1 ;
        }
        for ( int j = i - 1 ; j > high ; j-- )
            a[j+1] = a[j] ;
        a [high+1] = temp ;
    }
}

void ShellSort(int arr[], int len)
{
    int i, j, temp, jump=len>>1;
    while (jump != 0)
    {
        for (i = jump; i < len; i++)
        {
            temp = arr[i];
            j = i - jump;
            while (j >= 0 && temp < arr[j])
            {
                arr[j + jump] = arr[j];
                j=j-jump;
            }
            arr[j + jump] = temp;
        }
        jump/=2;;
    }
}


void CountingSort(int a[],int n)
{
    int m = GetMax(a,n);
    int b[m+1]={0};
    for(int j=0;j<n;j++)   b[a[j]]++;
    for(int i=0,k=0;i<=m||k<n;i++)
    {
        while(b[i]>0){
            a[k++] = i;
            b[i]--;
        }
    } 
}

void RadixSort(int*a,int length)
{
    int max=a[0];
    for(int i=1;i<length;i++)
    {
        if(a[i]>max)
        {
            max=a[i];
        }
    }
    int base=1;
    int *b=(int*)malloc(sizeof(int)*length);
    int i;
    while(max/base>0)
    {
        int t[10]={0};
        for(i=0;i<length;i++)
        {
            t[a[i]/base%10]++;
        }
        for(i=1;i<10;i++)
        {
            t[i]+=t[i-1];
        }
        for(i=length-1;i>=0;i--)
        {
            b[t[a[i]/base%10]-1]=a[i];
            t[a[i]/base%10]--;
        }
        for(i=0;i<length;i++)
        {
            a[i]=b[i];
        }
        base=base*10;
    }
}

void InsertSort(int* a, int n)
{
    int i = 0;
    for (i = 0; i < n - 1; i++)
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (tmp < a[end])
            {
                a[end + 1] = a[end];
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

void BubbleSort(int a[],int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                int t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
            }
        }
    }
}

void SelectSort(int arry[], int len)
{      
    int i;
    int j;
    for ( i = 0; i < len-1; i++)
    {
        int min = i;
        for (j = i + 1; j < len; j++)
        {
           if (arry[j] < arry[min])
            {
                min = j;
            }
        }
        int temp = arry[min];
        arry[min] = arry[i];
        arry[i] = temp;
    }
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];

    cout<<endl<<endl; 

    cout<<"数组a中有";

    MergeSort(a,0,n-1);
    cout<<ans;
    stable_sort(a,a+n);

    cout<<"队逆序对";

    cout<<endl<<endl;

    RadixSort(a,n);

    CountingSort(a,n);

    ShellSort(a,n);

    MergeFindSort(a,n);

    InsertSort(a,n);

    BubbleSort(a,n);

    SelectSort(a,n);



    QuickSort(a,0,n-1);
    sort(a,a+n);

    for(int i=0;i<n;i++)
       cout<<a[i]<<" ";
    return 0;
}

`