# Mergesort and some claims on comparison

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).