Merge sort is the best choice. At a first appearance, merge sort may be a good selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists.
It is reasonable to expect that you cannot do any better than O(N log N) in running time, whenever we use comparison based sorts.
However, the interesting part is to investigate if you can sort it in-place, stably, and so on.
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.
It may be possible, depending on a number of factors, it may actually be faster to copy the list to an array and then use a Quicksort.
The reason this might be faster is that an array has much better cache performance than a linked list. If the nodes in the list are dispersed in memory, you may be generating cache misses all over the place. Then again, if the array is large you will get cache misses anyway.
Mergesort parallelises better, so it may be a better choice if that is what you want. It is also much faster if you perform it directly on the linked list.
Since both algorithms run in O(n * log n), making an informed decision would involve profiling them both on the machine you would like to run them on.
Here are some methods for sorting on linked list:
Thanks.
It is reasonable to expect that you cannot do any better than O(N log N) in running time, whenever we use comparison based sorts.
However, the interesting part is to investigate if you can sort it in-place, stably, and so on.
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.
It may be possible, depending on a number of factors, it may actually be faster to copy the list to an array and then use a Quicksort.
The reason this might be faster is that an array has much better cache performance than a linked list. If the nodes in the list are dispersed in memory, you may be generating cache misses all over the place. Then again, if the array is large you will get cache misses anyway.
Mergesort parallelises better, so it may be a better choice if that is what you want. It is also much faster if you perform it directly on the linked list.
Since both algorithms run in O(n * log n), making an informed decision would involve profiling them both on the machine you would like to run them on.
Here are some methods for sorting on linked list:
- Merge sort on linked list
- bubble sort on linked list
- quick sort on linked list
- Insertion sort on linked list
- Selection sort on linked list
Thanks.
0 comments:
Post a Comment