# Mergesort and some claims on comparison

Computer Science Asked by user3661613 on February 7, 2021

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(nlog n)$$ sorting algorithm: such an algorithm performs $$O(nlog 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(nlog 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).

Answered by Yuval Filmus on February 7, 2021

## Related Questions

### How to generate graphs with a Hamiltonian path?

3  Asked on February 21, 2021 by always-newbie

### Wifi throughput calculation

1  Asked on February 20, 2021 by copsa

### Searching for points near given point in a multidimensional space

1  Asked on February 20, 2021 by saku

### Group adjacent sections to create groups with biggest value, value is changing in groups

1  Asked on February 20, 2021 by rossko_dca

### Thirty-one game. Prediction of the winner

1  Asked on February 17, 2021 by donvitomarco

### Explanation of conventional solutions to the Firing Squad Synchronization problem

0  Asked on February 16, 2021 by von-spotz

### If $B$ is worse than $A$ on some inputs, how do their worst-case time complexities compare?

1  Asked on February 13, 2021 by aviv-barel

### How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

5  Asked on February 10, 2021 by gizmo

### Complexity of a cutting operation on a list of binary trees

0  Asked on February 10, 2021 by arthur-b

### speed of preorder traversal

1  Asked on February 8, 2021 by keith-paton

### Mergesort and some claims on comparison

1  Asked on February 7, 2021 by user3661613

### Proving the language of non-primes is in NP

1  Asked on February 6, 2021 by builderthebob00

### Does writing more data to disk consume more energy than writing less?

0  Asked on February 5, 2021 by pookie

### In Strassen’s algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

1  Asked on February 4, 2021 by retsek680

### How to find the language of a CFG from Production rules

1  Asked on February 3, 2021 by stark2022

### Machine Learning algorithm for predicting a user’s rating on an item?

0  Asked on February 1, 2021 by david-grnberger

### Finding the Hamiltonian cycle that uses the least amount of straight lines

0  Asked on January 30, 2021 by tzlil

### Can I have 2 free adjacent nodes in the fit algorithm for data management

0  Asked on January 29, 2021 by angelic-demonic

### Longest path on a full tree

1  Asked on January 27, 2021 by bm1125