//ABcDexter
#include<bits/stdc++.h>
using namespace std;
int count=0; //count function calls
int MedianOf3P(int a[],int p, int r)
{
int x=a[p],y=a[(r-p)/2+p],z=a[r-1],i=p-1,j=r;
if (y>x && y<z || y>z && y<x ) x=y;
else if (z>x && z<y || z>y && z<x ) x=z;
while (true)
{
do {j--;} while (a[j] > x);
do {i++;} while (a[i] < x);
if (i < j) std::swap(a[i],a[j]);
else return j+1;
}
}
void QuickSort_Median(int a[],int start,int end)
{
int pivot;
if (end-start<2) return;
pivot=MedianOf3P(a,start,end);
::count++; /*function call*/ QuickSort_Median(a,start,pivot);
::count++; /*function call*/ QuickSort_Median(a,pivot,end);
}
int i,n,t;
int main(){
n=15; int A[n];
for(i=0,t=1048576;i<n;i++)
{ A[i]=(rand()%t);
}
for(i=0;i<n;i++)
cout<<A[i]<<",";
QuickSort_Median(A,0,n); cout<<"\nsorted:\n";
for(i=0;i<n;i++)
cout<<A[i]<<",";
cout<<"Ans : "<<::count<<endl;
}
Ly9BQmNEZXh0ZXIKI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBjb3VudD0wOyAvL2NvdW50IGZ1bmN0aW9uIGNhbGxzCgppbnQgTWVkaWFuT2YzUChpbnQgYVtdLGludCBwLCBpbnQgcikgCnsKICAgIGludCB4PWFbcF0seT1hWyhyLXApLzIrcF0sej1hW3ItMV0saT1wLTEsaj1yOwogICAgaWYgKHk+eCAmJiB5PHogfHwgeT56ICYmIHk8eCApIHg9eTsKICAgIGVsc2UgaWYgKHo+eCAmJiB6PHkgfHwgej55ICYmIHo8eCApIHg9ejsKICAgIHdoaWxlICh0cnVlKSAKICAgIHsKICAgICAgICBkbyAge2otLTt9IHdoaWxlIChhW2pdID4geCk7CiAgICAgICAgZG8gIHtpKys7fSB3aGlsZSAoYVtpXSA8IHgpOwogICAgICAgIGlmICAoaSA8IGopIHN0ZDo6c3dhcChhW2ldLGFbal0pOwogICAgICAgIGVsc2UgcmV0dXJuIGorMTsKICAgIH0KfQp2b2lkIFF1aWNrU29ydF9NZWRpYW4oaW50IGFbXSxpbnQgc3RhcnQsaW50IGVuZCkgCnsKICAgIGludCBwaXZvdDsKICAgIGlmIChlbmQtc3RhcnQ8MikgcmV0dXJuOwogICAgcGl2b3Q9TWVkaWFuT2YzUChhLHN0YXJ0LGVuZCk7CiAgICA6OmNvdW50Kys7IC8qZnVuY3Rpb24gY2FsbCovIFF1aWNrU29ydF9NZWRpYW4oYSxzdGFydCxwaXZvdCk7CiAgICA6OmNvdW50Kys7IC8qZnVuY3Rpb24gY2FsbCovIFF1aWNrU29ydF9NZWRpYW4oYSxwaXZvdCxlbmQpOwp9CgppbnQgaSxuLHQ7CmludCBtYWluKCl7CgluPTE1OyBpbnQgQVtuXTsKCWZvcihpPTAsdD0xMDQ4NTc2O2k8bjtpKyspCgl7CUFbaV09KHJhbmQoKSV0KTsKCX0KCWZvcihpPTA7aTxuO2krKykKCQljb3V0PDxBW2ldPDwiLCI7CgkJCglRdWlja1NvcnRfTWVkaWFuKEEsMCxuKTsgY291dDw8Ilxuc29ydGVkOlxuIjsKCWZvcihpPTA7aTxuO2krKykKCQljb3V0PDxBW2ldPDwiLCI7Cgljb3V0PDwiQW5zIDogIjw8Ojpjb3VudDw8ZW5kbDsKCQp9
738663,730054,825449,215155,56401,613631,562250,350444,925481,556237,743610,972715,82418,466683,174563,
sorted:
56401,82418,174563,215155,350444,466683,556237,562250,613631,730054,738663,743610,825449,925481,972715,Ans : 28