1. Introduction
The linked list is, due to its relative simplicity, a commonly seen data structure in computer science.
In this tutorial, we’ll show the most efficient ways to sort linked lists.
2. Linked Lists
One of the advantages of using linked lists is that the insertion and removal of elements require only constant time (that is, 
) updates of the neighboring elements, whereas other structures such as arrays would require a reordering of the elements in the collection.
Conversely, access or lookup of an element is in linear time (that is, 
, where 
is the size of the list), as the references of the items need to be traversed in order to find the target element. This is considered a poor characteristic for sorting, as common ‘swap’ operations are less efficient, and the pointers of the list can be spread around in memory. This results, in theory, in poor sorting performance when compared to an array.
3. Fastest Algorithms for Sorting Linked Lists
We’ll consider two comparative sorting algorithms for linked lists. Comparative algorithms are bounded by a time-complexity of 
, the lower bound for sorting algorithms in the general case. We also consider the non-comparative Radix sort as an option:
- Quicksort: a divide-and-conquer, non-stable sorting algorithm that employs a pivot to split the list into recursively sorted sub-arrays consisting of elements greater and less than the pivot, respectively
- Merge sort: a divide-and-conquer, stable sorting algorithm that works by recursively creating sub-lists for every element in the list
- Radix sort (also known as bucket sort or digital sort) is a non-comparative non-stable sorting algorithm
3.1. Qualitative Analysis
Merge is best for problems requiring low space, as we can implement it for linked lists with constant auxiliary space requirements. 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. Converting a linked list to an array can also improve speed by enabling the usage of cache optimizations, as there is a higher chance of cache misses when using a linked list due to the distribution of the pointers in memory. Then we do need to account for the space and run-time requirements of converting the linked list to an array and back.
In certain special situations, the Radix sort is better suited for sorting large lists since 
could be smaller than the logarithm of . The speed of the Radix sort depends on the context, however, as the key size affects the time-complexity of the algorithm and depends on the type of the objects that need to be sorted.
3.2. Quantitative Analysis
Since Radix sort is more suited for specific problems with large lists, we will not consider it in the benchmark below. In order to give some insight, we benchmark Quicksort for linked lists and arrays and Merge sort for linked lists in Python 3. The Merge sort algorithm is the iterative bottom-up approach. The sorts are run five times for various sizes, indicated by the columns of the table. The results of the five runs are averaged. We can see the results in the table below:
10k
100k
1000k
Quicksort (ARR)
0.0208s
0.256s
3.60s
Quicksort (LL)
0.0308s
0.412s
6.99s
Merge sort (LL)
0.0540s
0.897s
11.60s
The results of the Merge sort for linked lists might not be indicative of the recursive approach. However, the recursive approach needs large amounts of recursive calls and is not suited for sorting large lists.
4. Conclusion
The efficiency of sorting algorithms depends on the type of objects that need to be sorted, the length of the list, and the specifics of the environment the sorting algorithm operates on. The Radix sort might be best if we have a large list of elements that can be represented with relatively small key sizes. If we have space restrictions and stable sort requirements or want to purely sort a linked list, Merge sort is the best option.
Finally, converting the linked list to an array and using Quicksort might be the fastest solution.