Menu
I'm curious if O(n log n) is the best a linked list can do.
855
Binary Search is usually fast and efficient for arrays because accessing the middle index between two given indices is easy and fast(Time Complexity O(1)).
But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
Basically, don't use quicksort with a linked-list style data structure. You want mergesort. Quicksort will always perform poorly for any data structure where random access is O(n).
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.
It is reasonable to expect that you cannot do any better than O(N log N) in running time.
However, the interesting part is to investigate whether you can sort it in-place, stably, its worst-case behavior and so on.
Simon Tatham, of Putty fame, explains how to sort a linked list with merge sort. He concludes with the following comments:
Like any self-respecting sort algorithm, this has running time O(N log N). Because this is Mergesort, the worst-case running time is still O(N log N); there are no pathological cases.
Auxiliary storage requirement is small and constant (i.e. a few variables within the sorting routine). Thanks to the inherently different behaviour of linked lists from arrays, this Mergesort implementation avoids the O(N) auxiliary storage cost normally associated with the algorithm.
There is also an example implementation in C that work for both singly and doubly linked lists.
As @Jørgen Fogh mentions below, big-O notation may hide some constant factors that can cause one algorithm to perform better because of memory locality, because of a low number of items, etc.
62
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
