TransWikia.com

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

One Answer

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP