Я решил проверить здесь примеры, а также еще один подход, изначально написанный Джонатаном Каннингемом в Pop-11. Я закодировал все подходы в C # и провел сравнение с рядом разных размеров списков. Я сравнил подход Mono eglib от Raja R Harinath, код C # от Shital Shah, подход Java от Jayadev, рекурсивные и нерекурсивные версии от David Gamble, первый код C от Ed Wynn (этот сбой произошел с моим примером набора данных, Я не отлаживал) и версию Каннингема. Полный код здесь: https://gist.github.com/314e572808f29adb0e41.git.
Mono eglib основан на идее, похожей на идею Каннингема, и имеет сравнимую скорость, если только список не отсортирован, и в этом случае подход Каннингема гораздо быстрее (если он частично отсортирован, eglib немного быстрее). Код eglib использует фиксированную таблицу для хранения рекурсии сортировки слиянием, тогда как подход Каннингема работает с использованием повышающихся уровней рекурсии - поэтому он начинается без рекурсии, затем рекурсии с 1 глубиной, затем рекурсии с 2 глубинами и так далее, в соответствии с сколько шагов нужно, чтобы сделать сортировку. Я считаю, что код Каннингема немного легче следовать, и нет никаких сомнений в том, насколько велика составление таблицы рекурсии, поэтому он получает мой голос. Другие подходы, которые я попробовал на этой странице, были в два или более раз медленнее.
Вот порт C # типа Pop-11:
/// <summary>
/// Sort a linked list in place. Returns the sorted list.
/// Originally by Jonathan Cunningham in Pop-11, May 1981.
/// Ported to C# by Jon Meyer.
/// </summary>
public class ListSorter<T> where T : IComparable<T> {
SingleListNode<T> workNode = new SingleListNode<T>(default(T));
SingleListNode<T> list;
/// <summary>
/// Sorts a linked list. Returns the sorted list.
/// </summary>
public SingleListNode<T> Sort(SingleListNode<T> head) {
if (head == null) throw new NullReferenceException("head");
list = head;
var run = GetRun(); // get first run
// As we progress, we increase the recursion depth.
var n = 1;
while (list != null) {
var run2 = GetSequence(n);
run = Merge(run, run2);
n++;
}
return run;
}
// Get the longest run of ordered elements from list.
// The run is returned, and list is updated to point to the
// first out-of-order element.
SingleListNode<T> GetRun() {
var run = list; // the return result is the original list
var prevNode = list;
var prevItem = list.Value;
list = list.Next; // advance to the next item
while (list != null) {
var comp = prevItem.CompareTo(list.Value);
if (comp > 0) {
// reached end of sequence
prevNode.Next = null;
break;
}
prevItem = list.Value;
prevNode = list;
list = list.Next;
}
return run;
}
// Generates a sequence of Merge and GetRun() operations.
// If n is 1, returns GetRun()
// If n is 2, returns Merge(GetRun(), GetRun())
// If n is 3, returns Merge(Merge(GetRun(), GetRun()),
// Merge(GetRun(), GetRun()))
// and so on.
SingleListNode<T> GetSequence(int n) {
if (n < 2) {
return GetRun();
} else {
n--;
var run1 = GetSequence(n);
if (list == null) return run1;
var run2 = GetSequence(n);
return Merge(run1, run2);
}
}
// Given two ordered lists this returns a list that is the
// result of merging the two lists in-place (modifying the pairs
// in list1 and list2).
SingleListNode<T> Merge(SingleListNode<T> list1, SingleListNode<T> list2) {
// we reuse a single work node to hold the result.
// Simplifies the number of test cases in the code below.
var prevNode = workNode;
while (true) {
if (list1.Value.CompareTo(list2.Value) <= 0) {
// list1 goes first
prevNode.Next = list1;
prevNode = list1;
if ((list1 = list1.Next) == null) {
// reached end of list1 - join list2 to prevNode
prevNode.Next = list2;
break;
}
} else { // same but for list2
prevNode.Next = list2;
prevNode = list2;
if ((list2 = list2.Next) == null) {
prevNode.Next = list1;
break;
}
}
}
// the result is in the back of the workNode
return workNode.Next;
}
}