Minimum questions to find sorted sequence

Question

Suppose two players A,B play a game.Person A knows a tuple of numbers in which the numbers can repeat ,let that tuple be $(x_{1},x_{2} ....,x_{n})=S$.Person B must try to identify sorted sequence of these numbers and he doesn't know them,no matter how long and he can ask A if $x_{i} \le x_{j} $ where $i,j$ are different.First person B asks questions and after all questions have been asked A tells him the answer to his questions.Then B for sure must know a sorted sequence of these numbers ,so the question is what is the minimum amount of questions B should ask?I am seeking a solution with a graph,I came up with the idea that if each number is vertex then we should try to find if this graph is connected which is known that the lower bound is $Ω(n^2)$,is my approach correct or is there a better one?

Answer 1

There are only $\frac12(n^2-n)$ pairs, so that is the most questions you need to ask. If you have to specify the questions before getting any answers, you need all of them because any pair could be neighbors in the order. If you can react to the data you get, there are sorting algorithms like heapsort that are $O(n \log n)$