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.
Join Stack Overflow to learn, share knowledge, and build your career.
|
|
Wonder why it should be big challenge as it is stated here, here is a straightforward implementation in Java with out any "clever tricks".
Some more explanation here - http://www.dontforgettothink.com/2011/11/23/merge-sort-of-linked-list |
|||||||||||||||||||||
|
|
A simpler/clearer implementation might be the recursive implementation, from which the NLog(N) execution time is more clear.
NB: This has a Log(N) storage requirement for the recursion. Performance should be roughly comparable with the other strategy I posted. There is a potential optimisation here by running the merge loop while (list && right), and simple appending the remaining list (since we don't really care about the end of the lists; knowing that they're merged suffices). |
||||
|
|
|
Heavily based on the EXCELLENT code from: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html Trimmed slightly, and tidied:
NB: This is O(NLog(N)) guaranteed, and uses O(1) resources (no recursion, no stack, nothing). |
|||||||||
|
|
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. |
|||
|
|
|
The simplest is from Gonnet + Baeza Yates Handbook of Algorithms. You call it with the number of sorted elements you want, which recursively gets bisected until it reaches a request for a size one list which you then just peel off the front of the original list. These all get merged up into a full sized sorted list. [Note that the cool stack-based one in the first post is called the Online Mergesort and it gets the tiniest mention in an exercise in Knuth Vol 3] |
|||
|
|
|
Here's an alternative recursive version. This does not need to step along the list to split it: we supply a pointer to a head element (which is not part of the sort) and a length, and the recursive function returns a pointer to the end of the sorted list.
|
|||||
|
|
I'd been obsessing over optimizing clutter for this algorithm and below is what I've finally arrived at. Lot of other code on Internet and StackOverflow is horribly bad. There are people trying to get middle point of the list, doing recursion, having multiple loops for left over nodes, maintaining counts of ton of things - ALL of which is unnecessary. MergeSort naturally fits to linked list and algorithm can be beautiful and compact but it's not trivial to get to that state. Below code maintains minimum number of variables and has minimum number of logical steps needed for the algorithm (i.e. without making code unmaintainable/unreadable) as far as I know. However I haven't tried to minimize LOC and kept as much white space as necessary to keep things readable. I've tested this code through fairly rigorous unit tests. Note that this answer combines few techniques from other answer https://stackoverflow.com/a/3032462/207661. While the code is in C#, it should be trivial to convert in to C++, Java, etc.
Points of interest
Update: @ideasman42 has translated above code to C/C++ along with suggestions for fixing comments and bit more improvement. Above code is now up to date with these. |
|||||||||||||||||||||
|
|
I decided to test the examples here, and also one more approach, originally written by Jonathan Cunningham in Pop-11. I coded all the approaches in C# and did a comparison with a range of different list sizes. I compared the Mono eglib approach by Raja R Harinath, the C# code by Shital Shah, the Java approach by Jayadev, the recursive and non-recursive versions by David Gamble, the first C code by Ed Wynn (this crashed with my sample dataset, I didn't debug), and Cunningham's version. Full code here: https://gist.github.com/314e572808f29adb0e41.git. Mono eglib is based on a similar idea to Cunningham's and is of comparable speed, unless the list happens to be sorted already, in which case Cunningham's approach is much much faster (if its partially sorted, the eglib is slightly faster). The eglib code uses a fixed table to hold the merge sort recursion, whereas Cunningham's approach works by using increasing levels of recursion - so it starts out using no recursion, then 1-deep recursion, then 2-deep recursion and so on, according to how many steps are needed to do the sort. I find the Cunningham code a little easier to follow and there is no guessing involved in how big to make the recursion table, so it gets my vote. The other approaches I tried from this page were two or more times slower. Here is the C# port of the Pop-11 sort:
|
|||||||||
|
|
Here is my implementation of Knuth's "List merge sort" (Algorithm 5.2.4L from Vol.3 of TAOCP, 2nd ed.). I'll add some comments at the end, but here's a summary: On random input, it runs a bit faster than Simon Tatham's code (see Dave Gamble's non-recursive answer, with a link) but a bit slower than Dave Gamble's recursive code. It's harder to understand than either. At least in my implementation, it requires each element to have TWO pointers to elements. (An alternative would be one pointer and a boolean flag.) So, it's probably not a useful approach. However, one distinctive point is that it runs very fast if the input has long stretches that are already sorted.
|
|||||||||||||||||
|
|
There's a non-recursive linked-list mergesort in mono eglib. The basic idea is that the control-loop for the various merges parallels the bitwise-increment of a binary integer. There are O(n) merges to "insert" n nodes into the merge tree, and the rank of those merges corresponds to the binary digit that gets incremented. Using this analogy, only O(log n) nodes of the merge-tree need to be materialized into a temporary holding array. |
|||||
|
|
Another example of a non-recursive merge sort for linked lists, where the functions are not part of a class. This example code and HP / Microsoft std::list::sort both use the same basic algorithm. A bottom up, non-recursive, merge sort that uses a small (26 to 32) array of pointers to the first nodes of a list, where array[i] is either 0 or points to a list of size 2 to the power i. On my system, Intel 2600K 3.4ghz, it can sort 4 million nodes with 32 bit unsigned integers as data in about 1 second.
|
||||
|
|
|
This is the entire Piece of code which shows how we can create linklist in java and sort it using Merge sort. I am creating node in MergeNode class and there is another class MergesortLinklist where there is divide and merge logic.
|
|||
|
|
|
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. |
|||
|
|
|
One of the drawback of the merge sort is that it uses up O(n) space to store the data. i.e. when you merge the two sublists For linked list, this can be avoided by keep changing the next pointer in the list node. The last implementation seems neat but fails to consider it. |
|||
|
|
|
|||||||||
|