views:

4049

answers:

11

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.

A: 

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

Bryan Roth
This clearly merge sorts an array..
Amit
A: 

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.

DShook
+2  A: 

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.

John the Statistician
+1  A: 
paperhorse
A: 

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

Amit
This is definitely not how to sort a linked list. The existence of the stable, guaranteed NLog(N), O(1) resource mergesort means that if you HAVE data in a linked list, you should DEFINITELY NOT copy it out. (Unless you have specific circumstances, such as the availability of a radix sort).
Dave Gamble
A: 

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

Tobias Langner
A: 

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

Christoph
A: 

I once have developed one for linked lists in Delphi:

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

Ritsaert Hornstra
+1  A: 

Here's another description, with an implementation in C

finnw
A: 
Dave Gamble
A: 
Dave Gamble