Sorting linked lists
Hi, im just wondering what method of sorting would be efficient for nodes in a doubly linked list to be sorted by their integer elements in ascending order?
Merge sort is commonly used to sort linked lists, and is very efficient with O(nlogn) time complexity in the average and (importantly) worst case.
Usually the method provided by the standard library of your language.
In a purely theoretical situation, if the list is almost sorted, insertion sort gets the best complexity. Otherwise, quicksort and merge sort are fairly good choices.
In a purely theoretical situation, if the list is almost sorted, insertion sort gets the best complexity. Otherwise, quicksort and merge sort are fairly good choices.
I'll second Merge Sort.
Quicksort is slightly easier to implement, but has an awful (n^2) worst-case (which can potentially be abused by hostile users).
However, if you're doing anything other than inserting once in bulk prior to a single sort you'd be much better off with a tree of some form, efficiency (and algorithmic-complexity) wise. Of course, trees are far harder to implement.
Quicksort is slightly easier to implement, but has an awful (n^2) worst-case (which can potentially be abused by hostile users).
However, if you're doing anything other than inserting once in bulk prior to a single sort you'd be much better off with a tree of some form, efficiency (and algorithmic-complexity) wise. Of course, trees are far harder to implement.
+1 to merge sort although depending on the size of your list you will probably be fine with a quick sort.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement