Sorting a linked list- why not? [closed]

开发者_JS百科 As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 11 years ago.

I was recently reading an article which mentioned:

For God's sake, don't try sorting a linked list during the interview.

Is there any reason why the author wrote this? The reason is not immediately clear. I am aware that merge sort works on linked lists in O(nlgn) time- what's wrong with that? Am I missing something obvious?

EDIT: Any reason why is question is voted to close? I'm honestly curious and merely looking for some answers or interesting points.

---

I have no way of knowing why the author of the blog wrote what he did. If I had to guess, I'd say what was really meant was something along the lines of:

Don't assume that efficiently sorting a linked list would be as easy as sorting a data structure that provides random access to its elements. If you do end up relying on being able to sort a linked list, be prepared to explain what a suitable algorithm might be, and to discuss its complexity.

---

I think you'll find that, although it's possible to sort a linked list using merge sort, the code to do so efficiently is somewhat involved. It's not something you'd want to develop while standing at the white board in the middle of an interview.

---

The operation of getting/setting elements at specific indices is used by most sorting algorithms, and are required to be fast in order for the sorting algorithms to be fast. Normally they are O(1) for say a normal list, but for a linked list it is O(n) and this makes the sorting terribly inefficient. Perhaps this captures the reasoning behind your quote.