1
$\begingroup$

Is Merge Sort the best sorting technique to sort a linked list? Also, which sorting technique is worst for a linked list?


Merge sort uses a divide and conquer method. What makes merge sort efficient for sorting a linked list?

$\endgroup$

closed as too broad by Evil, xskxzr, dkaeae, Discrete lizard Jun 5 at 10:10

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ It sounds like you have a couple of different questions. I recommend that you post your questions separately, rather than putting them all in the same post. Potentially separate questions are: (1) What is the run-time of merge sort on a linked list (2) What does "divide a conquer" mean? Use merge sort of a linked list as an example in your explanation. (3) Which sorting technique is worst for a linked list? Which algorithm is worst not a good question, but it was one that you asked. "What technique is best for sorting a linked list?" is another bad question, but you seem to be asking it $\endgroup$ – Toothpick Anemone May 30 at 16:52
1
$\begingroup$

It is really inefficient to access a certain index in a linked list, which is what many sorting algorithms rely on. MergeSort, however, divides and merges lists, which LLs do efficiently. You can find some code and an explanation here.

$\endgroup$
  • $\begingroup$ I cannot understand that code. Plz write code if possible $\endgroup$ – Srestha Apr 29 at 15:00
  • $\begingroup$ What language are you looking for? Or are there problems with the pseudocode? $\endgroup$ – TheEye Apr 29 at 15:08
  • $\begingroup$ I mean why merge sort efficient is not clear to me still now $\endgroup$ – Srestha Apr 29 at 15:48
  • $\begingroup$ In an array, for instance, it is very easy to access the i-th element, but it is very hard to add elements, because you would have to resize the array and move every element after the new one over.With linked lists, you can add or remove elements in constant time, because you only have to manipulate the element before and the one after. Accessing a certain index is harder, though, becaus you have to iterate through all the elements before. Because MergeSort uses concatenation of lists rather than accessing indices, it operates more efficiently on linked lists. $\endgroup$ – TheEye Apr 29 at 15:55
  • $\begingroup$ but how merge sorting on linked list? $\endgroup$ – Srestha Apr 29 at 17:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.