Why is mergesort better for linked lists?

Question

Why is mergesort considered "the way to go" when sorting lists and not quicksort? I heard this in a lecture that I watched online, and saw it in a couple of websites.

Subsidize

Check this out #498294 – Fescennine

Answer 1

One of the main sources of efficiency in quicksort is locality of reference, where the computer hardware is optimized so that accessing memory locations that are near one another tends to be faster than accessing memory locations scattered throughout memory. The partitioning step in quicksort typically has excellent locality, since it accesses consecutive array elements near the front and the back. As a result, quicksort tends to perform much better than other sorting algorithms like heapsort even though it often does roughly the same number of comparisons and swaps, since in the case of heapsort the accesses are more scattered.

Additionally, quicksort is typically much faster than other sorting algorithms because it operates in-place, without needing to create any auxiliary arrays to hold temporary values. Compared to something like merge sort, this can be a huge advantage because the time required to allocate and deallocate the auxiliary arrays can be noticeable. Operating in-place also improves quicksort's locality.

When working with linked lists, neither of these advantages necessarily applies. Because linked list cells are often scattered throughout memory, there is no locality bonus to accessing adjacent linked list cells. Consequently, one of quicksort's huge performance advantages is eaten up. Similarly, the benefits of working in-place no longer apply, since merge sort's linked list algorithm doesn't need any extra auxiliary storage space.

That said, quicksort is still very fast on linked lists. Merge sort just tends to be faster because it more evenly splits the lists in half and does less work per iteration to do a merge than to do the partitioning step.

Hope this helps!

Cardoon

In the last line of 3rd paragraph you wrote "Similarly, the benefits of working in-place no longer apply, since merge sort's linked list algorithm doesn't need any extra auxiliary storage space.". Why does it not need the auxilliary storage space? – Oberheim

@Oberheim I probably should have said "merge sort's linked list algorithm doesn't need O(n) auxiliary storage space." The standard array-based merge algorithm requires that you allocate extra storage space in the course of doing a merge because the elements need to be moved around. In merge sort with linked lists, it's possible to move elements around without allocating an external array by simply relinking them. – Cardoon

Answer 2

The cost of find() is more harmful to quicksort than mergesort.

Merge sort performs more "short range" operations on the data, making it more suitable for linked lists, whereas quicksort works better with random access data structure.

Niece

What do you mean by find()? – Cardoon

Seeking entries in the data structure. For a linked linst you are always advancing/rewinding, like playing a tape. – Niece

You don't need to use the random-access partition function used on arrays for quicksort in the linked list case. You can partition the linked list by iterating across the list and distributing each element into one of three lists - a "less than" list, a "greater-than" list, and an "equal list," then recursing on the latter two. You're right that the standard partition is slow, but that doesn't inherently make the linked list quicksort slow. – Cardoon

Answer 3

It is more memory efficient, that's why. Speed wise, it is slower. Linked lists have to iterate, through each element to get to the desired element, the only elements that can be accessed directly are the first element and the last element, in the case of a doubly linked list and this will make the addition and deletion faster, at the first and last elements of the list, otherwise it will be slower because it will have to iterate through each element to get to the specified index.

Arrays on the other hand are less, memory efficient, because the number of elements that it can hold is fixed and as a result, if not all of the spaces available in an array are not used, then the space is wasted, because when an array is created, the number of elements of the selected data type specified at the declaration will be allocated. Arrays are less efficient in deleting and adding data, because after the data has been added or deleted, the whole array must be re-arranged. On the other hand, arrays can access elements a lot faster, O(1) time complexity to be exact.

So in conclusion, arrays have faster overall search times, the deletion and addition times have a O(m - n + 1) time complexity in all cases, where "m" is the size of the array and "n" is the desired element index. Linked lists have O(1) addition and deletion times at the first and last element, but what is in between the time complexity is is worst, because it has to iterate through each element of the list, to get to that element. Linked lists have the best memory allocation, because linked list can change its size at runtime.

CREDIT: https://mcmap.net/q/1007910/-why-is-insertion-and-deletion-faster-in-a-linked-list-compared-to-an-array

Business