suppose for $n$ elements we using mergesort.
each number compared at most $O(\log n)$ = False
in average each element compared with $O(\log n)$ elements = True
there exist an element compared with $\Omega (\log n)$ elements = True
is there anyone can share idea about these facts (i.e: why first is false and others is true).
For the first fact, consider the array $1,\ldots,n,n+1,\ldots,2n$. Sorting its two halves doesn't alter the array. When the two halves are merged, the element $n+1$ would be compared against all elements in the left half.
The second fact is true for every $O(n\log n)$ sorting algorithm: such an algorithm performs $O(n\log n)$ comparisons overall, and so $O(\log n)$ comparisons per element on average.
The third fact is true for every comparison-based algorithm: any such algorithm must perform $\Omega(n\log n)$ comparisons, and so $\Omega(\log n)$ comparisons per element on average; in particular, some element is compared $\Omega(\log n)$ times.
Finally, let us note that the AKS sorting network corresponds to a sorting algorithm which performs $O(\log n)$ comparisons per element (since its depth is $O(\log n)$, and each element can only be compared once in each layer).
