Menu
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.
628
It turns out that Mergesort works even better on linked lists than it does on arrays. It avoids the need for the auxiliary space, and becomes a simple, reliably O(N log N) sorting algorithm. And as an added bonus, it's stable too.
Merge sort is preferred for linked lists over arrays. In the case of a linked list, the insert operation takes only O(1) time and space complexity which implies that we can implement the merge operation in constant time.
Merge sort is more efficient and works faster than quick sort in case of larger array size or datasets. Quick sort is more efficient and works faster than merge sort in case of smaller array size or datasets. Sorting method : The quick sort is internal sorting method where the data is sorted in main memory.
Generally speaking, merge sort is best suited for linked lists. This is due to the nature of the algorithm requiring less random access of memory. Quicksort can be fast but unreliable. Quicksort for arrays is a better option than for linked lists; the lookup times of arrays are faster than for linked lists.
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!
82
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.
40
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
