Merge Sort a Linked List

Question

I was recently brushing up on some fundamentals and found merge sorting a linked list to be a pretty good challenge. If you have a good implementation then show it off here.

Answer 1

Take a peek at this implementation of a merge sort. Hope this helps.

Answer 2

You can use that implementation of merge sort and write your own functions to interface with the linked list as if it were an array.

Answer 3

One interesting way is to maintain a stack, and only merge if the list on the stack has the same number of elements, and otherwise push the list, until you run out of elements in the incoming list, and then merge up the stack.

Answer 4

A simple, quick and "it works" way is to copy the linked list elements into a array, sort it and then re-create the linked list back. However, such a solution won't work straight away if you have got for than one member in your node, such as:

struct node {
   int data1;
   int data2;
   struct node *next;
};

This one works for me: http://bitbucket.org/amitksaha/foobar-scripts/src/f732216b9649/merge-sort-struct.c

Answer 5

look at: http://www.sorting-algorithms.com/merge-sort

Answer 6

A recursive version is straight-forward. I'm currently working on an iterative one, but it's still buggy.

Answer 7

I once have developed one for linked lists in Delphi:

http://www.continuit.nl/index.php?LANGUAGE=EN&PAGE=DOCUMENTS_SORTING

Answer 8

Here's another description, with an implementation in C