What’s the fastest algorithm for sorting a linked list?

by

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.

More Related Contents:

  1. Merge Sort a Linked List
  2. Sorting in linear time? [closed]
  3. Why is bubble sort O(n^2)?
  4. How to apply binary search O(log n) on a sorted linked list?
  5. Complexity of absolute difference and sum
  6. C++ Sorting Algorithms [closed]
  7. Priority scoring algorithm [closed]
  8. Efficient way to add element to sorted datastructure [closed]
  9. How can I pair socks from a pile efficiently?
  10. Big O, how do you calculate/approximate it?
  11. What is stability in sorting algorithms and why is it important?
  12. How can building a heap be O(n) time complexity?
  13. Is there an O(n) integer sorting algorithm?
  14. How does finding a cycle start node in a cycle linked list work?
  15. What would cause an algorithm to have O(log log n) complexity?
  16. What is Constant Amortized Time?
  17. Optimal algorithm for returning top k values from an array of length N
  18. How to rank a million images with a crowdsourced sort
  19. Sort Four Points in Clockwise Order
  20. Quicksort vs heapsort
  21. Faster version of find for sorted vectors (MATLAB)
  22. Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
  23. Can an array be grouped more efficiently than sorted?
  24. Search a sorted 2D matrix [duplicate]
  25. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  26. Comparison-based ranking algorithm
  27. how to determine if the kth largest element of the heap is greater than x
  28. Do iterative and recursive versions of an algorithm have the same time complexity?
  29. Computational complexity of base conversion
  30. Stable separation for two classes of elements in an array

Leave a Comment