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$
  • 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 '19 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 '19 at 15:00
  • $\begingroup$ What language are you looking for? Or are there problems with the pseudocode? $\endgroup$ – TheEye Apr 29 '19 at 15:08
  • $\begingroup$ I mean why merge sort efficient is not clear to me still now $\endgroup$ – Srestha Apr 29 '19 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 '19 at 15:55
  • $\begingroup$ but how merge sorting on linked list? $\endgroup$ – Srestha Apr 29 '19 at 17:12

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