#include<bits/stdc++.h>

using namespace std;

void quicksort(int input[],int low,int high,int& cnt,int t){

if(low>=high)

return ;

int mid=(low+high)/2;

int pivot=input[mid];

int i=low,j=high;

int temp;

while(i<j){

if(input[i]>=pivot && input[j]<=pivot){

temp=input[j];

input[j]=input[i];

input[i]=temp;

i++;

j--;

cnt++;

}

else{

i++;

}

for(int i=0;i<t;i++){

cout<<input[i]<<" ";

}

cout<<"\n";

}

quicksort(input,low,mid,cnt,t);

quicksort(input,mid+1,high,cnt,t);

}

int main()

{

int t;

cout<<"Enter size of Input array : ";

cin>>t;

int input[t];

cout<<"Enter space separated Elements of array : "

for(int i=0;i<t;i++)

cin>>input[i];

int cnt = 0;

quicksort(input,0,t-1,cnt,t);

cout<<"\nSorted Input Array is : ";

for(int i=0;i<t;i++)

cout<<input[i]<<" ";

cout<<"\nNumber of swaps : " <<cnt;

return 0;

}