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

StackExchange Computer Science Q#132916, answer score: 5