Computational Equivalence Between the Problems of Sorting and Monotone Reconstruction for Random Permutations

In this note,it is shown that the monotone reconstruction problem is equi-valent to that of sorting,in the sense of computational complexity.In particularfrom any given sorting al gorithm A,an algorithm B for the monotone reconstruc-tion problem can be developed with at most O(m)time and O(m)space cost morethan that used in A,and vice versa.As a consequence of this result,it is obtai-ned that the time complexity of the monotone reconstruction problem of n-ele-ment random perm utations is O(nlogn).