Do not sort a linked list

Leave a comment

May 18, 2016 by oneOokay

Why would it be a bad idea to sort a linked list? A few things come to mind:

  1. 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.
  2. 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:

http://fisherlei.blogspot.com/2013/12/leetcode-sort-list-solution.html

See original post here:

http://jonisalonen.com/2013/sorting-a-linked-list/

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: