http://gate.iitd.ac.in/qp2020.php
Exactly my point, even the word maintained is used. So why can't all elements be inserted in the linked list and then sorted using merge sort. You will definitely call it that after inserting n elements in an empty linked list, it has been maintained in sorted order. Benefit of doubt must be given to the examinee if what they wanted to imply was that linked list should be kept in sorted order after every insertion.
@johncenaoriginal Agreed. But won't you call a room that is all neat and clean a well maintained room. I can understand what you are trying to say, I myself have changed this answer from n^2 to nlogn while reviewing precisely because an answer which was asymptotically tighter was present. Try re reading the question after reading what I have said without any cognitive bias, you will understand what I am trying to say.
@amanjuyal Both can be the answer depending on how you interpret the question. If extra DS can be allowed then look at Vimal Patel's answer under the question, if you have the elements available before hand then look at the offline sorting technique which people are talking about and if you think that the word maintained can have another meaning like I am arguing above and elsewhere on the Internet, you can go for it. These are three major arguments that can work in favour of nlogn.
64.3k questions
77.9k answers
244k comments
80.0k users