I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm wrong):
binary-search(A,x): A=-∞ A[n+1]=∞ //|A|=n l=0 h=n+1 m=⌊(l+h)/2⌋ while (h != l+1) if (x<=A[m]) h=m else l=m m=⌊(l+h)/2⌋ return h //success if A[h]=x fun-sort(A): for i=1 to n: success=false while (!success): success=true h=binary-search(A,A[i]) if (A[h]!=A[i]): success=false if (i<(h-1)): swap(i,h-1) elif (i>h): swap(i,h)
As you can see, this sorting algorithm uses a binary search on a not necessarily sorted array. I realized that to get the average-case running time for Fun-sort, I needed the average number of iterations for its while cycle which I defined to be a random variable X. X would be geometrically distributed, so E[X]=1/p, where p is the probability of success of the binary-search procedure. I am stuck trying to get this probability of success.
So... any help would be very much appreciated =)
EDIT: I've been considering that binary-search will definitely fail when i < m and A[i]<=A[m]. In fact, every time the elements being compared in binary-search are an inversion, it will fail (thanks to Jorge M.). In other words, binary-search will end up in success if (x,A[m]) is not an inversion in each of the log n iterations. Now: what is the probability of (x,A[m]) being an inversion, in general?
EDIT2: I posted this on stackoverflow before I realized cs.stackexchange was a better option.