May 18, 2016 by oneOokay
Why would it be a bad idea to sort a linked list? A few things come to mind:
- To locate the kth item you have to traverse the k-1 items that precede it. This makes the formulation of many sorting algorithms unusable for linked lists: the basic “
swap"operation no longer takes constant time.
- Linked lists are inefficient in general: going over the items in a list means jumping around memory in random. This is bad for the CPU caches, and it might be faster to copy the linked list into an array, and then sort the array.
But let’s not be discouraged: in defiance of Steve, let’s sort a linked list, and do it efficiently, with minimal cache misses!
Another way to sort the linked list:
instead of using fast & slow pointers to get the median,
sort first the first 2 items of the list with the
merge operation, then the next 2, merge these so that the first 4 items are sorted, repeat for the next 4 elements and merge so that the first 8 items are sorted, and so on until the end.
a similar solution is given from here as well:
See original post here: